package com.example.leetcode.graph.common;

import com.example.leetcode.graph.common.unionfind.onedimension.pro.optimize.UnionFind;
import com.example.leetcode.tree.common.TreeNode;
import com.example.leetcode.tree.common.TreeUtils;
import javafx.util.Pair;

import java.util.*;

public class GraphUtils {

    public static Node buildGraph(int[][] adjList) {
        if (adjList == null || adjList.length == 0) {
            return null;
        }

        // 使用 Map 存储所有节点（val -> Node）
        Map<Integer, Node> nodeMap = new HashMap<>();

        // 先创建所有节点
        for (int i = 0; i < adjList.length; i++) {
            int val = i + 1;
            nodeMap.putIfAbsent(val, new Node(val));
        }

        // 添加邻居关系
        for (int i = 0; i < adjList.length; i++) {
            int val = i + 1;
            Node current = nodeMap.get(val);
            for (int neighborVal : adjList[i]) {
                current.neighbors.add(nodeMap.get(neighborVal));
            }
        }

        // 返回第一个节点（val = 1）
        return nodeMap.get(1);
    }

    // 生成邻接矩阵（邻接列表形式）
    public static int[][] exportAdjList(Node node) {
        if (node == null) return new int[0][0];

        // 由于 Node.val 是唯一且在 1 ~ 100 范围内，我们使用 Map 来记录访问过的节点
        Map<Integer, List<Integer>> adjMap = new HashMap<>();
        Set<Integer> visited = new HashSet<>();
        Queue<Node> queue = new LinkedList<>();

        queue.offer(node);
        visited.add(node.val);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            adjMap.putIfAbsent(curr.val, new ArrayList<>());

            for (Node neighbor : curr.neighbors) {
                adjMap.get(curr.val).add(neighbor.val);
                if (!visited.contains(neighbor.val)) {
                    visited.add(neighbor.val);
                    queue.offer(neighbor);
                }
            }
        }

        // 构造邻接列表数组
        int size = adjMap.keySet().stream().max(Integer::compare).orElse(0);
        int[][] adjList = new int[size][];

        for (int i = 1; i <= size; i++) {
            List<Integer> neighbors = adjMap.getOrDefault(i, new ArrayList<>());
            adjList[i - 1] = neighbors.stream().mapToInt(Integer::intValue).toArray();
        }

        return adjList;
    }

    public static int shortestBridge(int[][] grid) {

        // grid n * n
        // 宽度 = 高度
        int n = grid.length;

        Queue<int[]> queue = new LinkedList<>();

        boolean findFlag = false;
        // 找到第一个岛的第一个位置
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = -1;
                    queue.add(newNode(i, j));
                    findFlag = true;
                    break;
                }
            }
            if (findFlag) {
                break;
            }
        }

        List<int[]> dir = new ArrayList<>();
        dir.add(newNode(0, 1));
        dir.add(newNode(0, -1));
        dir.add(newNode(1, 0));
        dir.add(newNode(-1, 0));

        List<int[]> isLand = new ArrayList<>();
        // 找到第一个岛的所有元素
        while (queue.size() > 0) {
            // 出队, 执行某些操作
            int[] head = queue.poll();
            int x = head[0];
            int y = head[1];
            // 加入第一个小岛的元素集合
            isLand.add(head);
            for (int[] ints : dir) {
                int newX = x + ints[0];
                int newY = y + ints[1];
                if (isOK(newX, n) && isOK(newY, n)) {
                    // 否则在此处的判断会导致重复添加队列中的元素
                    if (grid[newX][newY] == 1) {
                        // 必须在入队的时候就标记被访问过
                        grid[newX][newY] = -1;
                        queue.add(newNode(newX, newY));
                    }
                }
            }
        }

        // 准备队列
        queue.clear();
        queue.addAll(isLand);

        // 以第一个岛为第一层向外扩张
        int step = 0;
        while (queue.size() > 0) {
            // 当前层的大小
            int levelSize = queue.size();
            // 遍历当前层的所有节点
            for (int i = 0; i < levelSize; i++) {
                // 当前层节点挨个出队
                int[] head = queue.poll();
                int x = head[0];
                int y = head[1];
                // 遍历当前节点的四周节点
                for (int[] ints : dir) {
                    int newX = x + ints[0];
                    int newY = y + ints[1];
                    if (isOK(newX, n) && isOK(newY, n)) {
                        // 遍历过程中存在某个节点为1, 说明找到了另一个小岛, 返回结果
                        if (grid[newX][newY] == 1) {
                            return step;
                        }
                        if (grid[newX][newY] == 0) {
                            grid[newX][newY] = -1;
                            // 下一层节点入队
                            queue.add(newNode(newX, newY));
                        }
                    }
                }
            }
            step++;
        }
        // -1表示不可达, 不存在第二个小岛
        return -1;
    }

    private static int[] newNode(int newX, int newY) {
        return new int[]{newX, newY};
    }

    private static boolean isOK(int pos, int max) {
        // 索引在 0-(n-1)之间为有效
        return pos >= 0 && pos <= max - 1;
    }

    public static int countComponents(int n, int[][] edges) {
        // graph中每一个List元素都表示一个节点,以及该节点所连接到的所有其他节点
        // 就是邻接表的存储方式
        List<List<Integer>> graph = new ArrayList<>();
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            graph.get(u).add(v); // 无向图边 (u,v)
            graph.get(v).add(u); // 无向图边 (v,u)
        }
        int count = 0;
        // 节点值从 0 到 n
        for (int u = 0; u < n; u++) {
            if (!visited[u]) {
                count++; // 只要顶点 u 此时尚未被访问，说明它不再此前的链路(连通分量)中，以它为新的连通分量起点
                dfs(u, visited, graph);
            }
        }
        return count;
    }

    private static void dfs(int u, boolean[] visited, List<List<Integer>> graph) {
        visited[u] = true;
        for (int v : graph.get(u)) {
            // v没有被访问过,进入v节点
            if (!visited[v]) dfs(v, visited, graph);
        }
    }

    public static int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        // 邻接表的存储方式
        // 红蓝色的图各需要一个邻接表
        List<Integer>[][] next = new List[2][n];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < n; j++) {
                next[i][j] = new ArrayList<>();
            }
        }
        for (int[] edge : redEdges) {
            next[0][edge[0]].add(edge[1]);
        }
        for (int[] edge : blueEdges) {
            next[1][edge[0]].add(edge[1]);
        }
        int[][] dist = new int[2][n]; // 两种类型的颜色最短路径的长度
        for (int i = 0; i < 2; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        Queue<int[]> queue = new ArrayDeque<>();
        dist[0][0] = 0;
        dist[1][0] = 0;
        queue.offer(new int[]{0, 0});
        queue.offer(new int[]{0, 1});
        while (!queue.isEmpty()) {
            int[] pair = queue.poll();
            int x = pair[0], t = pair[1];
            for (int y : next[1 - t][x]) {
                if (dist[1 - t][y] != Integer.MAX_VALUE) {
                    continue;
                }
                dist[1 - t][y] = dist[t][x] + 1;
                queue.offer(new int[]{y, 1 - t});
            }
        }
        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            answer[i] = Math.min(dist[0][i], dist[1][i]);
            if (answer[i] == Integer.MAX_VALUE) {
                answer[i] = -1;
            }
        }
        return answer;
    }

    public static int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] isVisited = new boolean[n];
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (!isVisited[i]) {
                // 选中一个新的省份的头一个城市
                isVisited[i] = true;
                // 往下遍历所有相连的城市
                dfs(isConnected, i, isVisited, n);
                result++;
            }
        }
        return result;
    }

    /**
     * 深度优先遍历一个省份
     *
     * @param isConnected
     * @param i
     * @param isVisited
     * @param n
     */
    private static void dfs(int[][] isConnected, int i, boolean[] isVisited, int n) {
        for (int j = 0; j < n; j++) {
            if (isConnected[i][j] == 1 && !isVisited[j]) {
                isVisited[j] = true;
                dfs(isConnected, j, isVisited, n);
            }
        }
    }

    public static int findCircleNum2(int[][] isConnected) {
        int n = isConnected.length;
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                queue.add(i);
                visited[i] = true;
                count++;
                while (queue.size() > 0) {
                    Integer curCity = queue.poll();
                    for (int j = 0; j < n; j++) {
                        if (isConnected[curCity][j] == 1 && !visited[j]) {
                            queue.add(j);
                            visited[j] = true;
                        }
                    }
                }
            }
        }
        return count;
    }

    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> curPath = new ArrayList<>();
        dfs(graph, 0, curPath, ans);
        return ans;
    }

    private static void dfs(int[][] graph, int i, List<Integer> curPath, List<List<Integer>> ans) {
        if (i == graph.length - 1) {
            curPath.add(i);
            ans.add(new ArrayList<>(curPath));
            curPath.remove(curPath.size() - 1);
            return;
        }
        for (int j = 0; j < graph[i].length; j++) {
            curPath.add(i);
            dfs(graph, graph[i][j], curPath, ans);
            curPath.remove(curPath.size() - 1);
        }
    }

    public static int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
        if (n == 1) {
            return 0;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < manager.length; i++) {
            if (manager[i] == -1) {
                continue;
            }
            List<Integer> list = map.get(manager[i]);
            if (list == null) {
                list = new ArrayList<>();
            }
            list.add(i);
            map.put(manager[i], list);
        }
        int[] ans = {0};
        dfs(map, headID, informTime, ans, 0);
        return ans[0];
    }

    private static void dfs(Map<Integer, List<Integer>> map, int curPeople, int[] informTime, int[] ans, int curTime) {
        List<Integer> list = map.get(curPeople);
        if (list == null) {
            ans[0] = Math.max(ans[0], curTime);
            return;
        }
        curTime += informTime[curPeople];
        for (Integer nextPeople : list) {
            dfs(map, nextPeople, informTime, ans, curTime);
        }
    }

    public static boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int n = rooms.size();
        boolean[] visited = new boolean[n];
        dfs(rooms, visited, 0);
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    private static void dfs(List<List<Integer>> rooms, boolean[] visited, int curRoom) {
        visited[curRoom] = true;
        List<Integer> list = rooms.get(curRoom);
        for (Integer room : list) {
            if (!visited[room]) {
                dfs(rooms, visited, room);
            }
        }
    }

    public static boolean canVisitAllRooms2(List<List<Integer>> rooms) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        set.add(0);
        queue.add(0);
        while (queue.size() > 0) {
            Integer curRoom = queue.poll();
            List<Integer> keys = rooms.get(curRoom);
            for (Integer key : keys) {
                if (!set.contains(key)) {
                    set.add(key);
                    queue.add(key);
                }
            }
        }
        return set.size() == rooms.size();
    }

    /**
     * 解法不对，对安全节点的理解有误
     * 图中可能存在环
     *
     * @param graph
     * @return
     */
    @Deprecated
    public static List<Integer> eventualSafeNodes1(int[][] graph) {
        int n = graph.length;
        Set<Integer> endNodes = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (graph[i].length == 0 || (graph[i].length == 1 && graph[i][0] == i)) {
                endNodes.add(i);
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int[] nodes = graph[i];
            boolean safe = true;
            for (int j = 0; j < nodes.length; j++) {
                if (!endNodes.contains(graph[i][j])) {
                    safe = false;
                    break;
                }
            }
            if (safe) {
                ans.add(i);
            }
        }
        return ans;
    }


    /**
     * 三色标记法
     * 0 未访问
     * 1 正在递归栈或者环中，如果最后未被置为2则表示不安全
     * 2 安全节点
     *
     * @param graph
     * @return
     */
    public static List<Integer> eventualSafeNodes(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (safe(graph, color, i)) {
                ans.add(i);
            }
        }
        return ans;
    }

    public static boolean safe(int[][] graph, int[] color, int curNode) {
        if (color[curNode] > 0) {
            return color[curNode] == 2;
        }
        color[curNode] = 1;
        for (int connectedNode : graph[curNode]) {
            if (!safe(graph, color, connectedNode)) {
                return false;
            }
        }
        color[curNode] = 2;
        return true;
    }

    /**
     * 反向图 + 拓扑排序
     *
     * @param graph
     * @return
     */
    public static List<Integer> eventualSafeNodes2(int[][] graph) {

        int n = graph.length;
        // 反向图
        List<List<Integer>> reverseGraph = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            reverseGraph.add(new ArrayList<>());
        }
        // 入度
        int[] inDegree = new int[n];
        // 遍历原图中的所有节点
        for (int x = 0; x < n; ++x) {
            // 构建反向图
            for (int y : graph[x]) {
                reverseGraph.get(y).add(x);
            }
            // 出度变入度
            inDegree[x] = graph[x].length;
        }

        Queue<Integer> queue = new LinkedList<>();
        // 让入度为0的点入队
        for (int i = 0; i < n; ++i) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()) {
            int y = queue.poll();
            // 获取所有相连的节点
            for (int x : reverseGraph.get(y)) {
                // 如果相连的节点入度减为了1，则入队
                if (--inDegree[x] == 0) {
                    queue.offer(x);
                }
            }
        }

        // 所有入度为0的节点就是拓扑序列中的节点，即为安全节点
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (inDegree[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }

    /**
     * 拓扑排序
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public static boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        // 初始化每个节点
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        // 构建图
        for (int[] prerequisite : prerequisites) {
            graph.get(prerequisite[0]).add(prerequisite[1]);
            // 统计入度
            inDegree[prerequisite[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        // 初始入度为0的节点入队
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        while (queue.size() > 0) {
            Integer curNode = queue.poll();
            List<Integer> connectedNodes = graph.get(curNode);
            for (Integer node : connectedNodes) {
                inDegree[node]--;
                // 相邻节点如果入度为0则入队
                if (inDegree[node] == 0) {
                    queue.add(node);
                }
            }
        }

        // 如果所有节点都在拓扑序列中，说明是有向无环图，不存在环，可以完成所有课程
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] > 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 输出拓扑序列
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public static int[] findOrder(int numCourses, int[][] prerequisites) {

        List<List<Integer>> graph = new ArrayList<>();
        int[] inDegree = new int[numCourses];
        // 初始化每个节点
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        // 构建图
        for (int[] prerequisite : prerequisites) {
            graph.get(prerequisite[1]).add(prerequisite[0]);
            // 统计入度
            inDegree[prerequisite[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        // 初始入度为0的节点入队
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        int[] result = new int[numCourses];
        int index = 0;
        while (queue.size() > 0) {
            Integer curNode = queue.poll();
            result[index] = curNode;
            index++;
            List<Integer> connectedNodes = graph.get(curNode);
            for (Integer node : connectedNodes) {
                inDegree[node]--;
                // 相邻节点如果入度为0则入队
                if (inDegree[node] == 0) {
                    queue.add(node);
                }
            }
        }

        // 如果拓扑序列的元素数量与图中的所有节点数量相同，说明存在合法的序列
        if (index == numCourses) {
            return result;
        } else {
            return new int[]{};
        }

    }

    /**
     * 容易忽略的是已经被通缉的过不能重复被通缉，与已经被访问过的节点相连的边无需再统计
     * 从0开始遍历，所有的边都应该指向之前被访问过的节点
     *
     * @param n
     * @param connections
     * @return
     */
    public static int minReorder(int n, int[][] connections) {
        // 根据边构建图
        // 有向无环图
        List<List<Integer>> graphWithDir = new ArrayList<>();
        // 无向无环图
        List<List<Integer>> graphNoDir = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graphWithDir.add(new ArrayList<>());
            graphNoDir.add(new ArrayList<>());
        }
        for (int[] board : connections) {
            // 有向图只需要给起点添加出度
            int start = board[0];
            int end = board[1];
            graphWithDir.get(start).add(end);
            // 无向图需要添加两个出度
            graphNoDir.get(start).add(end);
            graphNoDir.get(end).add(start);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        int ans = 0;
        while (queue.size() > 0) {
            Integer curNode = queue.poll();
            // 获取相连的所有节点
            List<Integer> connectedNodes = graphNoDir.get(curNode);
            // 获取所有的出边
            List<Integer> outNodes = graphWithDir.get(curNode);
            for (Integer node : connectedNodes) {
                // 某条出边已经被统计过，则不再重复统计
                if (!visited[node] && outNodes.contains(node)) {
                    ans++;
                }
                // 相邻的所有节点未被访问过都需要入队
                if (!visited[node]) {
                    queue.add(node);
                    visited[node] = true;
                }
            }
        }
        return ans;
    }

    public static int nearestExit(char[][] maze, int[] entrance) {
        int m = maze.length;
        int n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.add(entrance);
        visited[entrance[0]][entrance[1]] = true;
        int step = 0;
        int[] x = {0, 0, 1, -1};
        int[] y = {1, -1, 0, 0};
        while (queue.size() > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curNode = queue.poll();
                int curX = curNode[0];
                int curY = curNode[1];
                if ((curX == 0 || curX == m - 1 || curY == 0 || curY == n - 1)
                    && !(curX == entrance[0] && curY == entrance[1])) {
                    return step;
                }
                for (int j = 0; j < 4; j++) {
                    int newX = curX + x[j];
                    int newY = curY + y[j];
                    // 越界
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    // 墙壁
                    if (maze[newX][newY] == '+') {
                        continue;
                    }
                    // 被访问过
                    if (visited[newX][newY]) {
                        continue;
                    }
                    queue.add(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
            step++;
        }
        return -1;
    }

    public static int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> visited = new HashSet<>();
        Set<String> bankSet = new HashSet<>();
        Collections.addAll(bankSet, bank);
        if (!bankSet.contains(endGene)) {
            return -1;
        }
        char[] genes = {'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        queue.add(startGene);
        visited.add(startGene);
        int step = -1;
        while (queue.size() > 0) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String curGene = queue.poll();
                if (curGene.equals(endGene)) {
                    return step;
                }
                // 让变化后的基因入队
                for (int j = 0; j < curGene.length(); j++) {
                    for (int k = 0; k < 4; k++) {
                        if (curGene.charAt(j) != genes[k]) {
                            // 替换字符
                            String newGene = curGene.substring(0, j) + genes[k] + curGene.substring(j + 1);
                            // 如果新基因在基因库中
                            if (bankSet.contains(newGene) && !visited.contains(newGene)) {
                                queue.add(newGene);
                                visited.add(newGene);
                            }
                        }
                    }
                }
            }
        }
        return -1;
    }

    public static boolean canReach(int[] arr, int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        boolean[] visited = new boolean[arr.length];
        visited[start] = true;
        while (queue.size() > 0) {
            Integer curPos = queue.poll();
            if (arr[curPos] == 0) {
                return true;
            }
            int left = curPos - arr[curPos];
            int right = curPos + arr[curPos];
            if (left >= 0 && left < arr.length && !visited[left]) {
                queue.add(left);
                visited[left] = true;
            }
            if (right >= 0 && right < arr.length && !visited[right]) {
                queue.add(right);
                visited[right] = true;
            }
        }
        return false;
    }

    /**
     * 超级0思路
     * 类似于最短路径超级源点
     * 将初始时所有的0看成一个整体
     * 构造一个超级0与所有的0直接相连，从超级0往外扩展
     *
     * @param mat
     * @return
     */
    public static int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        boolean[][] visited = new boolean[m][n];
        int[][] ans = new int[m][n];
        Queue<int[]> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        int[] xDir = {0, 0, 1, -1};
        int[] yDir = {1, -1, 0, 0};
        int step = -1;
        while (queue.size() > 0) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curPos = queue.poll();
                int curX = curPos[0];
                int curY = curPos[1];
                ans[curX][curY] = step;
                for (int j = 0; j < 4; j++) {
                    int newX = curX + xDir[j];
                    int newY = curY + yDir[j];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    if (visited[newX][newY]) {
                        continue;
                    }
                    if (mat[newX][newY] == 1) {
                        queue.add(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
        }
        return ans;
    }

    public static int shortestPathBinaryMatrix(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (grid[0][0] == 1 || grid[m - 1][n - 1] == 1) {
            return -1;
        }
        // 包含四个边四个角八个格子
        int[] xDir = {0, 0, 1, -1, -1, -1, 1, 1};
        int[] yDir = {1, -1, 0, 0, -1, 1, -1, 1};
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        queue.add(new int[]{0, 0});
        visited[0][0] = true;
        int step = 0;
        while (queue.size() > 0) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] curPos = queue.poll();
                int curX = curPos[0];
                int curY = curPos[1];
                if (curX == m - 1 && curY == n - 1) {
                    return step;
                }
                for (int j = 0; j < 8; j++) {
                    int newX = curX + xDir[j];
                    int newY = curY + yDir[j];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    if (visited[newX][newY]) {
                        continue;
                    }
                    if (grid[newX][newY] == 0) {
                        queue.add(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
        }
        return -1;
    }

    public static List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        // 构建无向图
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, Boolean> visited = new HashMap<>();
        List<TreeNode> nodes = TreeUtils.getTreeNodesByMidTraverse(root);
        for (TreeNode curNode : nodes) {
            int key = curNode.val;
            graph.putIfAbsent(key, new ArrayList<>());
            if (curNode.left != null) {
                graph.get(key).add(curNode.left.val);
                graph.putIfAbsent(curNode.left.val, new ArrayList<>());
                graph.get(curNode.left.val).add(key);
            }
            if (curNode.right != null) {
                graph.get(key).add(curNode.right.val);
                graph.putIfAbsent(curNode.right.val, new ArrayList<>());
                graph.get(curNode.right.val).add(key);
            }
        }
        int start = target.val;
        // BFS扫描图
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited.put(start, true);
        int step = -1;
        List<Integer> ans = new ArrayList<>();
        while (queue.size() > 0) {
            step++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Integer curNode = queue.poll();
                if (step == k) {
                    ans.add(curNode);
                }
                List<Integer> connectedNodes = graph.get(curNode);
                for (Integer node : connectedNodes) {
                    if (!visited.getOrDefault(node, false)) {
                        queue.add(node);
                        visited.put(node, true);
                    }
                }
            }
            if (step == k) {
                break;
            }
        }
        return ans;
    }

    public static int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        int[] xDir = {0, 0, 1, -1};
        int[] yDir = {1, -1, 0, 0};
        while (true) {
            int startX = -1;
            int startY = -1;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == '1' && !visited[i][j]) {
                        startX = i;
                        startY = j;
                        break;
                    }
                }
                if (startX != -1) {
                    break;
                }
            }
            if (startX == -1) {
                break;
            }
            ans++;
            queue.add(new int[]{startX, startY});
            visited[startX][startY] = true;
            while (queue.size() > 0) {
                int[] curPos = queue.poll();
                int curX = curPos[0];
                int curY = curPos[1];
                for (int i = 0; i < 4; i++) {
                    int newX = curX + xDir[i];
                    int newY = curY + yDir[i];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    if (visited[newX][newY]) {
                        continue;
                    }
                    if (grid[newX][newY] == '1') {
                        queue.add(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
        }
        return ans;
    }

    public static int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 1) {
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        int[] xDir = {0, 0, 1, -1};
        int[] yDir = {1, -1, 0, 0};
        while (queue.size() > 0) {
            int[] curPos = queue.poll();
            int curX = curPos[0];
            int curY = curPos[1];
            for (int i = 0; i < 4; i++) {
                int newX = curX + xDir[i];
                int newY = curY + yDir[i];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                    continue;
                }
                if (visited[newX][newY]) {
                    continue;
                }
                if (grid[newX][newY] == 1) {
                    queue.add(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    ans++;
                }
            }
        }
        return ans;
    }

    public static int closedIsland(int[][] grid) {
        // 先将与边界相连的陆地打上标记
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && grid[i][j] == 0) {
                    queue.add(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }
        int[] xDir = {0, 0, 1, -1};
        int[] yDir = {1, -1, 0, 0};
        while (queue.size() > 0) {
            int[] curPos = queue.poll();
            int curX = curPos[0];
            int curY = curPos[1];
            for (int i = 0; i < 4; i++) {
                int newX = curX + xDir[i];
                int newY = curY + yDir[i];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                    continue;
                }
                if (visited[newX][newY]) {
                    continue;
                }
                if (grid[newX][newY] == 0) {
                    queue.add(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }

        int ans = 0;
        // 再统计剩余部分岛屿的数量即为封闭岛屿的数量
        while (true) {
            int startX = -1;
            int startY = -1;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 0 && !visited[i][j]) {
                        startX = i;
                        startY = j;
                        break;
                    }
                }
                if (startX != -1) {
                    break;
                }
            }
            if (startX == -1) {
                break;
            }
            ans++;
            queue.add(new int[]{startX, startY});
            visited[startX][startY] = true;
            while (queue.size() > 0) {
                int[] curPos = queue.poll();
                int curX = curPos[0];
                int curY = curPos[1];
                for (int i = 0; i < 4; i++) {
                    int newX = curX + xDir[i];
                    int newY = curY + yDir[i];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    if (visited[newX][newY]) {
                        continue;
                    }
                    if (grid[newX][newY] == 0) {
                        queue.add(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
        }
        return ans;
    }

    public static int maxAreaOfIsland(int[][] grid) {

        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        int[] xDir = {0, 0, 1, -1};
        int[] yDir = {1, -1, 0, 0};
        int ans = 0;
        while (true) {
            int startX = -1;
            int startY = -1;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1 && !visited[i][j]) {
                        startX = i;
                        startY = j;
                        break;
                    }
                }
                if (startX != -1) {
                    break;
                }
            }
            if (startX == -1) {
                break;
            }
            int temp = 0;
            queue.add(new int[]{startX, startY});
            visited[startX][startY] = true;
            while (queue.size() > 0) {
                int[] curPos = queue.poll();
                temp++;
                int curX = curPos[0];
                int curY = curPos[1];
                for (int i = 0; i < 4; i++) {
                    int newX = curX + xDir[i];
                    int newY = curY + yDir[i];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    if (visited[newX][newY]) {
                        continue;
                    }
                    if (grid[newX][newY] == 1) {
                        queue.add(new int[]{newX, newY});
                        visited[newX][newY] = true;
                    }
                }
            }
            ans = Math.max(ans, temp);
        }
        return ans;

    }

    /**
     * pacificAtlantic1() 方法抽取代码优化后得到的新方法
     *
     * @param heights
     * @return
     */
    public static List<List<Integer>> pacificAtlantic(int[][] heights) {

        int m = heights.length;
        int n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        Queue<int[]> queue1 = new LinkedList<>();
        Queue<int[]> queue2 = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    queue1.add(new int[]{i, j});
                    pacific[i][j] = true;
                }
                if (i == m - 1 || j == n - 1) {
                    queue2.add(new int[]{i, j});
                    atlantic[i][j] = true;
                }
            }
        }

        // 从太平洋开始扩散
        bfs(heights, pacific, queue1);

        // 从大西洋开始扩散
        bfs(heights, atlantic, queue2);

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i);
                    pos.add(j);
                    ans.add(pos);
                }
            }
        }
        return ans;

    }

    private static void bfs(int[][] heights, boolean[][] visited, Queue<int[]> queue) {
        int[] xDir = {0, 0, 1, -1};
        int[] yDir = {1, -1, 0, 0};
        int m = heights.length;
        int n = heights[0].length;
        while (queue.size() > 0) {
            int[] curPos = queue.poll();
            int curX = curPos[0];
            int curY = curPos[1];
            for (int i = 0; i < 4; i++) {
                int newX = curX + xDir[i];
                int newY = curY + yDir[i];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                    continue;
                }
                if (visited[newX][newY]) {
                    continue;
                }
                if (heights[newX][newY] >= heights[curX][curY]) {
                    queue.add(new int[]{newX, newY});
                    visited[newX][newY] = true;
                }
            }
        }
    }

    public static List<List<Integer>> pacificAtlantic1(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];
        int[] xDir = {0, 0, 1, -1};
        int[] yDir = {1, -1, 0, 0};

        Queue<int[]> queue = new LinkedList<>();

        // 从太平洋开始扩散
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    queue.add(new int[]{i, j});
                    pacific[i][j] = true;
                }
            }
        }
        while (queue.size() > 0) {
            int[] curPos = queue.poll();
            int curX = curPos[0];
            int curY = curPos[1];
            for (int i = 0; i < 4; i++) {
                int newX = curX + xDir[i];
                int newY = curY + yDir[i];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                    continue;
                }
                if (pacific[newX][newY]) {
                    continue;
                }
                if (heights[newX][newY] >= heights[curX][curY]) {
                    queue.add(new int[]{newX, newY});
                    pacific[newX][newY] = true;
                }
            }
        }

        // 从大西洋开始扩散
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == m - 1 || j == n - 1) {
                    queue.add(new int[]{i, j});
                    atlantic[i][j] = true;
                }
            }
        }
        while (queue.size() > 0) {
            int[] curPos = queue.poll();
            int curX = curPos[0];
            int curY = curPos[1];
            for (int i = 0; i < 4; i++) {
                int newX = curX + xDir[i];
                int newY = curY + yDir[i];
                if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                    continue;
                }
                if (atlantic[newX][newY]) {
                    continue;
                }
                if (heights[newX][newY] >= heights[curX][curY]) {
                    queue.add(new int[]{newX, newY});
                    atlantic[newX][newY] = true;
                }
            }
        }

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    List<Integer> pos = new ArrayList<>();
                    pos.add(i);
                    pos.add(j);
                    ans.add(pos);
                }
            }
        }
        return ans;

    }

    public static int findJudge(int n, int[][] trust) {
        int[] inDegree = new int[n + 1];
        int[] outDegree = new int[n + 1];
        for (int i = 0; i < trust.length; i++) {
            outDegree[trust[i][0]]++;
            inDegree[trust[i][1]]++;
        }
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == n - 1 && outDegree[i] == 0) {
                return i;
            }
        }
        return -1;
    }

    public static List<Integer> findSmallestSetOfVertices(int n, List<List<Integer>> edges) {
        int[] inDegree = new int[n];
        for (List<Integer> edge : edges) {
            inDegree[edge.get(1)]++;
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                ans.add(i);
            }
        }
        return ans;
    }

    public static int maximalNetworkRank(int n, int[][] roads) {
        // 构建无向图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        // 记录节点的度
        int[] degree = new int[n];
        for (int[] road : roads) {
            int from = road[0];
            int to = road[1];
            graph.get(from).add(to);
            graph.get(to).add(from);
            degree[from]++;
            degree[to]++;
        }
        // 找到度最大的城市
        PriorityQueue<Pair<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
        for (int i = 0; i < n; i++) {
            queue.add(new Pair<>(i, degree[i]));
        }
        int ans = 0;
        Pair<Integer, Integer> first = queue.poll();
        Pair<Integer, Integer> second = queue.poll();
        List<Pair<Integer, Integer>> list = new ArrayList<>();
        list.add(first);
        list.add(second);
        while (queue.size() > 0 && Objects.equals(queue.peek().getValue(), second.getValue())) {
            list.add(queue.poll());
        }
        // 枚举所有可能产生结果的城市对
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                int temp = list.get(i).getValue() + list.get(j).getValue();
                if (graph.get(list.get(i).getKey()).contains(list.get(j).getKey())) {
                    temp--;
                }
                ans = Math.max(ans, temp);
            }
        }
        return ans;
    }

    /**
     * 红蓝染色法，能够顺利给所有节点染色则能二分，出现染色冲突则不能二分
     *
     * @param graph
     * @return
     */
    public static boolean isBipartite(int[][] graph) {
        int n = graph.length;
        char[] color = new char[n];
        Queue<Integer> queue = new LinkedList<>();
        while (true) {
            int start = -1;
            for (int i = 0; i < n; i++) {
                if (color[i] != 'r' && color[i] != 'g') {
                    start = i;
                    break;
                }
            }
            if (start == -1) {
                break;
            }
            color[start] = 'r';
            queue.add(start);
            while (queue.size() > 0) {
                Integer curNode = queue.poll();
                char curColor = color[curNode];
                char nextColor = curColor == 'r' ? 'g' : 'r';
                int[] connectedNodes = graph[curNode];
                for (int connectedNode : connectedNodes) {
                    if (color[connectedNode] == curColor) {
                        return false;
                    }
                    if (color[connectedNode] == nextColor) {
                        continue;
                    }
                    queue.add(connectedNode);
                    color[connectedNode] = nextColor;
                }
            }
        }
        return true;
    }

    /**
     * 判断无向图是树，则要求图没有环并且是连通图
     *
     * @param n
     * @param edges
     * @return
     */
    public static boolean validTree(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            graph.get(from).add(to);
            graph.get(to).add(from);
        }
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        visited[0] = true;
        while (queue.size() > 0) {
            Integer curNode = queue.poll();
            List<Integer> connectedNodes = graph.get(curNode);
            int count = 0;
            for (int i = 0; i < connectedNodes.size(); i++) {
                Integer node = connectedNodes.get(i);
                if (visited[node]) {
                    count++;
                    if (count > 1) {
                        return false;
                    }
                    continue;
                }
                queue.add(node);
                visited[node] = true;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 哈希表 + 并查集
     *
     * @param accounts
     * @return
     */
    public static List<List<String>> accountsMerge(List<List<String>> accounts) {
        // 每个邮箱对应的编号
        Map<String, Integer> emailToIndex = new HashMap<>();
        // 每个邮箱对应的名称
        Map<String, String> emailToName = new HashMap<>();
        int emailsCount = 0;
        for (List<String> account : accounts) {
            // 账户名
            String name = account.get(0);
            int size = account.size();
            // 遍历账户下的所有邮箱
            for (int i = 1; i < size; i++) {
                String email = account.get(i);
                // 如果邮箱没有出现过
                // 如果同一个邮箱在不同的账户中重复出现，则会判断邮箱已经存在，不会重复加入哈希表
                // 同时，题目保证同一个人所有账户的账户名是一样的，所以同一个邮箱无需重复加入哈希表
                if (!emailToIndex.containsKey(email)) {
                    // 邮箱编号从0开始  [0,n-1]
                    emailToIndex.put(email, emailsCount++);
                    emailToName.put(email, name);
                }
            }
        }

        // n个邮箱，并查集节点数量也是n
        UnionFind uf = new UnionFind(emailsCount);

        // 遍历所有的账户，进行账户合并
        // 如果两个账户下存在同一个邮箱，说明两个账户属于同一个用户，那么由于编号相同，两个账户下的所有邮箱会合并成一个连通分量
        // 最终合并完成后，得到的就是题目所求答案，连通分量的数量就是最终的不同用户的数量，此时同一个人的所有账户已经合并完成
        for (List<String> account : accounts) {
            // 拿到账户下的第一个邮箱
            String firstEmail = account.get(1);
            // 拿到邮箱的编号
            int firstIndex = emailToIndex.get(firstEmail);
            int size = account.size();

            // 遍历账户后续的所有邮箱
            for (int i = 2; i < size; i++) {
                String nextEmail = account.get(i);
                // 拿到邮箱编号
                int nextIndex = emailToIndex.get(nextEmail);
                // 与第一个邮箱编号进行合并
                uf.union(firstIndex, nextIndex);
            }
        }

        Map<Integer, List<String>> indexToEmails = new HashMap<>();
        // 遍历所有的邮箱
        for (String email : emailToIndex.keySet()) {
            // 获取邮箱编号
            Integer curIndex = emailToIndex.get(email);
            // 查询编号的根节点编号
            int rootIndex = uf.find(curIndex);
            List<String> account = indexToEmails.getOrDefault(rootIndex, new ArrayList<>());
            account.add(email);
            // 建立根节点编号与对应连通分量下所有邮箱的映射关系
            indexToEmails.put(rootIndex, account);
        }

        // 查询哈希表，给邮箱排序并添加用户名生成账户信息，加入结果集输出
        List<List<String>> result = new ArrayList<>();
        for (List<String> emails : indexToEmails.values()) {
            // 对一个人的所有邮箱进行排序
            Collections.sort(emails);
            // 随便找个邮箱获取用户名
            String name = emailToName.get(emails.get(0));
            // 生成最终的一条结果
            List<String> account = new ArrayList<>();
            account.add(name);
            account.addAll(emails);
            // 加入结果集
            result.add(account);
        }

        return result;
    }

    public static int findCircleNum3(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.rootCount();
    }

    public static boolean equationsPossible(String[] equations) {
        UnionFind unionFind = new UnionFind(26);
        // 如果是等式，则合并两个变量的编号
        for (String equation : equations) {
            if (equation.charAt(1) == '=') {
                unionFind.union(equation.charAt(0) - 'a', equation.charAt(3) - 'a');
            }
        }
        // 待所有等式合并完毕
        // 如果是不等式，判断两个变量是否属于同一个连通分量
        for (String equation : equations) {
            if (equation.charAt(1) == '!' && unionFind.isConnected(equation.charAt(0) - 'a', equation.charAt(3) - 'a')) {
                return false;
            }
        }
        return true;
    }

    public static String smallestEquivalentString(String s1, String s2, String baseStr) {
        UnionFind unionFind = new UnionFind(26);
        for (int i = 0; i < s1.length(); i++) {
            unionFind.union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }
        // 获取所有的连通分量
        Map<Integer, List<Integer>> connectedComponent = unionFind.getAllConnectedComponent();
        // 对连通分量进行排序，ascii码靠前意味着字典序也靠前
        for (List<Integer> list : connectedComponent.values()) {
            Collections.sort(list);
        }
        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < baseStr.length(); i++) {
            int root = unionFind.find(baseStr.charAt(i) - 'a');
            char c = (char) (connectedComponent.get(root).get(0) + 97);
            ans.append(c);
        }
        return ans.toString();
    }

    /**
     * 动态规划
     * 最短路径对所经过的边或者点的数量有限制时只能使用动态规划，如果没有限制可以使用 Bellman-Ford 算法，SPFA 算法来求解源点到其他节点的最短距离
     *
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k
     * @return
     */
    public static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        Map<Integer, List<Edge>> graph = new HashMap<>();
        // 初始化图中的所有节点
        for (int i = 0; i < n; i++) {
            graph.put(i, new ArrayList<>());
        }
        // 构建图
        for (int[] flight : flights) {
            int from = flight[0];
            int to = flight[1];
            int weight = flight[2];
            Edge edge = new Edge(from, to, weight, true);
            // 每个节点只记录入边，不记出边
            graph.get(to).add(edge);
        }
        // dp数组含义为 从src出发，经过最多row条边，到达col点所经过的最短路径长度
        int[][] dp = new int[n][n];
        // 初始化dp数组
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        // 递推边界，当边数为0时，到达自身的最短路径为0，到达其他点的最短路径依旧是无穷大
        dp[0][src] = 0;
        // 当最多经过的边数为[1, n-1]时
        for (int edgeCount = 1; edgeCount < dp.length; edgeCount++) {
            for (int targetCity = 0; targetCity < dp[0].length; targetCity++) {
                // 无论多少条边，到达自身的最短距离总是0
                if (targetCity == src) {
                    dp[edgeCount][targetCity] = 0;
                    continue;
                }
                // 遍历所有相邻的入边
                List<Edge> edges = graph.get(targetCity);
                for (Edge edge : edges) {
                    // 如果到达上一个节点的最短距离是无穷大，则在正权图中，到达当前节点的路径必然也会无穷大，不用更新dp数组
                    // 否则会出现数值溢出
                    if (dp[edgeCount - 1][edge.from] < Integer.MAX_VALUE) {
                        dp[edgeCount][targetCity] = Math.min(dp[edgeCount][targetCity], dp[edgeCount - 1][edge.from] + edge.weight);
                    }
                }
            }
        }
        // 中间最多经过 n-2 个中转站
        if (k > n - 2) {
            k = n - 2;
        }
        if (dp[k + 1][dst] == Integer.MAX_VALUE) {
            return -1;
        }
        return dp[k + 1][dst];
    }

    /**
     * 迪杰斯特拉算法 dijkstra
     *
     * @param times
     * @param n
     * @param k
     * @return
     */
    public static int networkDelayTime(int[][] times, int n, int k) {
        int N = 110;
        // 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
        int[][] w = new int[N][N];
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        // 记录哪些点已经被更新过
        boolean[] vis = new boolean[N];
        int INF = 0x3f3f3f3f;

        // 初始化邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 不相连的顶点间权重都赋值无穷大
                w[i][j] = w[j][i] = i == j ? 0 : INF;
            }
        }
        // 存图
        for (int[] t : times) {
            int u = t[0], v = t[1], c = t[2];
            w[u][v] = c;
        }

        // 最短路
        dijkstra(n, k, w, dist, vis, INF);

        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        return ans > INF / 2 ? -1 : ans;
    }

    /**
     * dijkstra 要求图中不能存在负权边，否则该算法无法给我们正确答案
     * 每次找到「最短距离最小」且「未被更新」的点t 以及 所有边的权重都不为负数 是保证答案正确的关键
     * 对于当前找到的点t，不存在别的路径到达点t的路径会更短了，当前找到的点t的最短距离就是最终的最终的最短距离
     *
     * @param n
     * @param k
     * @param w
     * @param dist
     * @param vis
     * @param INF
     */
    private static void dijkstra(int n, int k, int[][] w, int[] dist, boolean[] vis, int INF) {
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        Arrays.fill(vis, false);
        // 所有点的最短距离赋值无穷大
        Arrays.fill(dist, INF);

        // 初始时，只有起点最短距离为 0
        dist[k] = 0;

        // n个节点，迭代 n 次
        for (int i = 1; i <= n; i++) {

            int t = -1;
            // 找到未被标记且当前距离最短的点
            for (int j = 1; j <= n; j++) {
                if (!vis[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            // n 次迭代，每次必然能够找到一个未被标记计算过的节点，因此结束上方循环后 t 不会等于 -1

            // 标记当前点已经被计算过
            vis[t] = true;

            // 更新与当前点相连的点的最短距离，看看是否比之前的更短
            for (int j = 1; j <= n; j++) {
                // 如果两个点之间不存在边，则权重赋值为无穷大，不会更新
                // 因为采取了数组的邻接矩阵的存图方式，所有需要遍历 n 次，实际上未相连的节点距离是无穷大，是肯定不会被计算出最短距离的
                // 因此最终的效果其实也只是更新了相连的节点的最短距离
                dist[j] = Math.min(dist[j], dist[t] + w[t][j]);
            }
        }
    }

    /**
     * Bellman Ford Algorithm 基础版 其实就是动态规划经过空间优化后的解法
     * 优化版无法解决这种路径受限的问题
     *
     * @param n
     * @param flights
     * @param src
     * @param dst
     * @param k
     * @return
     */
    public static int findCheapestPrice1(int n, int[][] flights, int src, int dst, int k) {
        // 源点与终点相同时
        if (src == dst) {
            return 0;
        }

        int[] previous = new int[n];
        int[] current = new int[n];
        // 初始化数组
        for (int i = 0; i < n; i++) {
            previous[i] = Integer.MAX_VALUE;
            current[i] = Integer.MAX_VALUE;
        }
        // 源点到源点是0
        previous[src] = 0;
        // k 个中转站，k + 1条边，循环 k+1 次
        for (int i = 1; i < k + 2; i++) {
            // 源点到源点总是0
            current[src] = 0;
            // 遍历所有的边
            for (int[] flight : flights) {
                // 边的起点
                int from = flight[0];
                // 边的终点
                int to = flight[1];
                // 权重
                int weight = flight[2];

                // 到达起点的最短距离不是无穷大时才尝试更新
                if (previous[from] < Integer.MAX_VALUE) {
                    // 更新终点的最短路径
                    current[to] = Math.min(current[to], previous[from] + weight);
                }
            }
            // 将当前的最短路径复制给p数组，后续循环在此基础上进行
            previous = current.clone();
        }
        return current[dst] == Integer.MAX_VALUE ? -1 : current[dst];
    }

    /**
     * 多源最短路径floyd算法
     *
     * @param ts
     * @param n
     * @param k
     * @return
     */
    public static int networkDelayTime1(int[][] ts, int n, int k) {
        int N = 110;
        // 邻接矩阵数组：w[a][b] = c 代表从 a 到 b 有权重为 c 的边
        int[][] w = new int[N][N];
        int INF = 0x3f3f3f3f;

        // 初始化邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 到自身的距离为0，到其他点的距离初始均为无穷大
                if (i == j) {
                    w[i][j] = w[j][i] = 0;
                } else {
                    w[i][j] = w[j][i] = INF;
                }
            }
        }

        // 存图
        for (int[] t : ts) {
            int from = t[0], to = t[1], weight = t[2];
            // 更新直接相连的两点之间的最短距离
            // 间接相连的点之间的最短距离后续更新
            w[from][to] = weight;
        }

        floyd(n, w);

        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            // 遍历得到k与其他点的最短距离
            ans = Math.max(ans, w[k][i]);
        }
        if (ans >= INF / 2) {
            return -1;
        }
        return ans;
    }

    /**
     * floyd算法，也称为插点法，不断向点(i,j)点对之间插入p点，进行松弛操作，更新最短距离，本质上也是枚举
     *
     * @param n
     * @param w
     */
    private static void floyd(int n, int[][] w) {
        // 最短路
        // floyd 基本流程为三层循环：
        // 枚举中转点 - 枚举起点 - 枚举终点 - 松弛操作
        for (int p = 1; p <= n; p++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    // 在 i 和 j 点之间 插入p点，进行松弛操作，更新两点之间的最短距离
                    w[i][j] = Math.min(w[i][j], w[i][p] + w[p][j]);
                }
            }
        }
    }


    /**
     * Bellman Ford 优化版
     *
     * @param times
     * @param n
     * @param k
     * @return
     */
    public static int networkDelayTime2(int[][] times, int n, int k) {

        // 使用 Bellman Ford 算法计算每个点的最短距离
        Map<Integer, Integer> shortestPathLength = bellmanFord(n, k, times);

        int ans = -1;
        // 遍历图得到答案
        for (Integer time : shortestPathLength.values()) {
            ans = Math.max(ans, time);
        }
        // 存在点的最短距离为无穷大，说明信号不能传递到所有节点
        if (ans == Integer.MAX_VALUE) {
            return -1;
        }
        return ans;

    }

    private static Map<Integer, Integer> bellmanFord(int n, int k, int[][] edges) {
        Map<Integer, Integer> shortestPathLength = new HashMap<>();
        // 初始化所有节点的最短路径为无穷大
        for (int i = 1; i <= n; i++) {
            shortestPathLength.put(i, Integer.MAX_VALUE);
        }
        // 源点的最短路径为0
        shortestPathLength.put(k, 0);
        // 遍历所有的边更新节点的最短路径
        for (int i = 0; i < n; i++) {
            // 在上一次结果的基础上计算新的最短距离
            Map<Integer, Integer> prev = new HashMap<>(shortestPathLength);
            boolean changed = false;
            for (int[] edge : edges) {
                int from = edge[0];
                int to = edge[1];
                int weight = edge[2];
                // 如果到达当前边的起点的位置就已经是无穷大了，则后续节点肯定无法更新最短距离，跳过当前边
                if (prev.get(from) == Integer.MAX_VALUE) {
                    continue;
                }
                Integer after = prev.get(from) + weight;
                Integer before = prev.get(to);
                if (after < before) {
                    shortestPathLength.put(to, after);
                    changed = true;
                }
            }
            if (!changed) {
                break;
            }
        }
        return shortestPathLength;
    }

    /**
     * 迪杰斯特拉算法
     *
     * @param times
     * @param n
     * @param k
     * @return
     */
    public static int networkDelayTime3(int[][] times, int n, int k) {
        List<List<Edge>> graph = new ArrayList<>();
        // 节点编号从 1 - n
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        // 构建有向图（不存在负权边）
        for (int[] ints : times) {
            int from = ints[0];
            int to = ints[1];
            int weight = ints[2];
            Edge edge = new Edge(from, to, weight, true);
            graph.get(from).add(edge);
        }

        // 使用 dijkstra 算法计算每个点的最短距离
        Map<Integer, Integer> shortestPathLength = dijkstra(n, k, graph);

        int ans = -1;
        // 遍历图得到答案
        for (Integer time : shortestPathLength.values()) {
            ans = Math.max(ans, time);
        }
        // 存在点的最短距离为无穷大，说明信号不能传递到所有节点
        if (ans == Integer.MAX_VALUE) {
            return -1;
        }
        return ans;
    }

    /**
     * 堆优化后的迪杰斯特拉算法
     *
     * @param times
     * @param n
     * @param k
     * @return
     */
    public static int networkDelayTime6(int[][] times, int n, int k) {
        List<List<Edge>> graph = new ArrayList<>();
        // 节点编号从 1 - n
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        // 构建有向图（不存在负权边）
        for (int[] ints : times) {
            int from = ints[0];
            int to = ints[1];
            int weight = ints[2];
            Edge edge = new Edge(from, to, weight, true);
            graph.get(from).add(edge);
        }

        // 使用 dijkstra 算法计算每个点的最短距离
        Map<Integer, Integer> shortestPathLength = dijkstra2(n, k, graph);

        int ans = -1;
        // 遍历图得到答案
        for (Integer time : shortestPathLength.values()) {
            ans = Math.max(ans, time);
        }
        // 存在点的最短距离为无穷大，说明信号不能传递到所有节点
        if (ans == Integer.MAX_VALUE) {
            return -1;
        }
        return ans;
    }

    /**
     * 使用堆优化的dijkstra算法
     *
     * @param n
     * @param k
     * @param graph
     * @return
     */
    private static Map<Integer, Integer> dijkstra2(int n, int k, List<List<Edge>> graph) {
        // 使用 dijkstra 算法计算每个点的最短距离
        Map<Integer, Integer> shortestPathLength = new HashMap<>();
        // 初始化所有点的最短距离为无穷大
        for (int i = 1; i <= n; i++) {
            shortestPathLength.put(i, Integer.MAX_VALUE);
        }
        // 初始化起点的最短距离是0，后续从0开始向外计算其他点的最短距离
        shortestPathLength.put(k, 0);
        // 所有点都设置成未被访问过
        boolean[] visited = new boolean[n + 1];

        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        // 将源点加入队列
        queue.add(new int[]{k, 0});
        while (queue.size() > 0) {
            int[] poll = queue.poll();
            int curNode = poll[0];
            if (visited[curNode]) {
                continue;
            }
            // 从队列中取到的节点的最短距离肯定不是无穷大
            int curLen = shortestPathLength.get(curNode);

            visited[curNode] = true;
            List<Edge> edges = graph.get(curNode);

            // 遍历所有相连的非负权边
            for (Edge edge : edges) {
                Integer beforeLen = shortestPathLength.get(edge.to);
                // 此处无需判断无穷大，即无需判断数值溢出
                int newLen = curLen + edge.weight;
                // 如果当前节点加上权重小于之前的距离，则更新最短距离
                if (newLen < beforeLen) {
                    shortestPathLength.put(edge.to, newLen);
                    // 将所有相连的最短距离有变更的节点加入队列
                    // 没有变更的点无需加入队列，没有变更的点相连的其他点的最短距离也会随着不会发生变更
                    // 思想类似于SPFA，使用队列优化的bellman ford算法
                    queue.add(new int[]{edge.to, newLen});
                }
            }
        }
        return shortestPathLength;
    }

    private static Map<Integer, Integer> dijkstra(int n, int k, List<List<Edge>> graph) {
        // 使用 dijkstra 算法计算每个点的最短距离
        Map<Integer, Integer> shortestPathLength = new HashMap<>();
        // 初始化所有点的最短距离为无穷大
        for (int i = 1; i <= n; i++) {
            shortestPathLength.put(i, Integer.MAX_VALUE);
        }
        // 初始化起点的最短距离是0，后续从0开始向外计算其他点的最短距离
        shortestPathLength.put(k, 0);
        // 所有点都设置成未被访问过
        boolean[] visited = new boolean[n + 1];
        for (int i = 0; i < n; i++) {
            int curNode = -1;
            // 认为整数最大值即为无穷大
            int curLen = Integer.MAX_VALUE;

            // 下方查找过程可以使用堆来完成，这样的话不需要每次都去遍历查找了
            // 将每个节点及其当前所得最短距离放入堆中
            // 找到一个未被计算完成的且当前距离最短的节点
            for (int j = 1; j <= n; j++) {
                if (visited[j]) {
                    continue;
                }
                Integer length = shortestPathLength.get(j);
                if (curNode == -1) {
                    curNode = j;
                    curLen = length;
                } else {
                    if (length < curLen) {
                        curNode = j;
                        curLen = length;
                    }
                }
            }

            visited[curNode] = true;
            List<Edge> edges = graph.get(curNode);

            // 遍历所有相连的非负权边
            for (Edge edge : edges) {
                Integer beforeLen = shortestPathLength.get(edge.to);
                // 上方找到的最短距离肯定不为无穷大，所以无需像bellman ford算法一样判断相加之后是否数值溢出
                int newLen = curLen + edge.weight;
                // 如果当前节点加上权重小于之前的距离，则更新最短距离
                if (newLen < beforeLen) {
                    shortestPathLength.put(edge.to, newLen);
                }
            }
        }
        return shortestPathLength;
    }


    public static int networkDelayTime4(int[][] ts, int n, int k) {
        int N = 110, M = 6010;
        // 邻接表
        int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        // 记录哪些点已经被更新过
        int idx = 0;
        int INF = 0x3f3f3f3f;

        // 初始化链表头
        Arrays.fill(he, -1);
        // 链式前向星存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            idx = add(he, e, ne, w, idx, u, v, c);
        }

        dijkstra(k, he, e, ne, w, dist, INF);

        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        if (ans > INF / 2) {
            return -1;
        }
        return ans;
    }

    private static int add(int[] he, int[] e, int[] ne, int[] w, int idx, int u, int v, int c) {
        e[idx] = v;
        ne[idx] = he[u];
        he[u] = idx;
        w[idx] = c;
        idx++;
        return idx;
    }

    /**
     * 堆优化版dijkstra算法
     *
     * @param k
     * @param he
     * @param e
     * @param ne
     * @param w
     * @param dist
     * @param INF
     */
    private static void dijkstra(int k, int[] he, int[] e, int[] ne, int[] w, int[] dist, int INF) {
        // 最短路
        // 起始所有的点「距离为正无穷」
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 使用「优先队列」存储所有可用于更新的点
        // 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点
        PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        q.add(new int[]{k, 0});
        while (!q.isEmpty()) {
            // 每次从「优先队列」中弹出
            int[] poll = q.poll();
            int id = poll[0];
            // 标记该点「已更新」，并使用该点更新其他点的「最短距离」
            for (int i = he[id]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[id] + w[i]) {
                    dist[j] = dist[id] + w[i];
                    q.add(new int[]{j, dist[j]});
                }
            }
        }
    }

    public static int networkDelayTime5(int[][] ts, int n, int k) {
        int N = 110;
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        // 表示权重无穷大
        int INF = 0x3f3f3f3f;
        // 使用类进行存边
        List<Edge> es = new ArrayList<>();
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            es.add(new Edge(u, v, c));
        }
        bellmanFord(n, k, dist, INF, es);
        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        if (ans > INF / 2) {
            return -1;
        }
        return ans;
    }

    /**
     * Bellman Ford
     *
     * @param n
     * @param k
     * @param dist
     * @param INF
     * @param es
     */
    private static void bellmanFord(int n, int k, int[] dist, int INF, List<Edge> es) {
        // 最短路
        // 起始先将所有的点标记为「距离为正无穷」
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 迭代 n 次，此处可以使用修改标记优化，当发生最短路径变更时，才进行下一次，否则可以结束算法了
        for (int p = 1; p <= n; p++) {
            // 每次都使用上一次迭代的结果，执行松弛操作
            int[] prev = dist.clone();
            // 遍历所有的边
            for (Edge edge : es) {
                int from = edge.from, to = edge.to, weight = edge.weight;
                dist[to] = Math.min(dist[to], prev[from] + weight);
            }
        }
    }

    public static int networkDelayTime7(int[][] ts, int n, int k) {
        int N = 110, M = 6010;
        // 邻接表
        int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
        // dist[x] = y 代表从「源点/起点」到 x 的最短距离为 y
        int[] dist = new int[N];
        // 记录哪一个点「已在队列」中
        boolean[] vis = new boolean[N];
        int INF = 0x3f3f3f3f;
        int idx = 0;

        // 初始化链表头
        Arrays.fill(he, -1);
        // 存图
        for (int[] t : ts) {
            int u = t[0], v = t[1], c = t[2];
            idx = add(he, e, ne, w, idx, u, v, c);
        }

        spfa(k, he, e, ne, w, dist, vis, INF);

        // 遍历答案
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = Math.max(ans, dist[i]);
        }
        if (ans > INF / 2) {
            return -1;
        }
        return ans;
    }

    /**
     * bellman ford算法的队列优化版 SPFA
     *
     * @param k
     * @param he
     * @param e
     * @param ne
     * @param w
     * @param dist
     * @param vis
     * @param INF
     */
    private static void spfa(int k, int[] he, int[] e, int[] ne, int[] w, int[] dist, boolean[] vis, int INF) {
        // 最短路
        // 起始先将所有的点标记为「未入队」和「距离为正无穷」
        Arrays.fill(vis, false);
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[k] = 0;
        // 使用「双端队列」存储，存储的是点编号
        Deque<Integer> d = new ArrayDeque<>();
        // 将「源点/起点」进行入队，并标记「已入队」
        d.addLast(k);
        vis[k] = true;
        // 类似于堆优化后的dijkstra算法
        while (!d.isEmpty()) {
            // 每次从「双端队列」中取出，并标记「未入队」
            int poll = d.pollFirst();
            vis[poll] = false;
            // 尝试使用该点，更新其他点的最短距离
            // 如果更新的点，本身「未入队」则加入队列中，并标记「已入队」
            for (int i = he[poll]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[poll] + w[i]) {
                    dist[j] = dist[poll] + w[i];
                    // 如果已经在队列中，则无需重复入队
                    if (vis[j]) {
                        continue;
                    }
                    d.addLast(j);
                    vis[j] = true;
                }
            }
        }
    }

    /**
     * bellman ford算法的队列优化版 SPFA
     *
     * @param times
     * @param n
     * @param k
     * @return
     */
    public static int networkDelayTime8(int[][] times, int n, int k) {
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] time : times) {
            int from = time[0];
            int to = time[1];
            int weight = time[2];
            Edge edge = new Edge(from, to, weight);
            graph.get(from).add(edge);
        }

        int[] dist = spfa(n, k, graph);

        int ans = -1;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, dist[i]);
        }
        return ans;
    }

    /**
     * SPFA 算法
     *
     * @param n
     * @param k
     * @param graph
     * @return
     */
    private static int[] spfa(int n, int k, List<List<Edge>> graph) {
        boolean[] inQueue = new boolean[n + 1];
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(k);
        dist[k] = 0;
        inQueue[k] = true;
        while (queue.size() > 0) {
            Integer curNode = queue.poll();
            inQueue[curNode] = false;
            List<Edge> edges = graph.get(curNode);
            for (Edge edge : edges) {
                int from = edge.from;
                int to = edge.to;
                int weight = edge.weight;
                if (dist[from] == Integer.MAX_VALUE) {
                    continue;
                }
                if (dist[to] > dist[from] + weight) {
                    dist[to] = dist[from] + weight;
                    // 如果节点最短距离被修改了，才需要判断是否入队
                    if (!inQueue[to]) {
                        queue.add(to);
                        inQueue[to] = true;
                    }
                }
            }
        }
        return dist;
    }

    /**
     * floyd算法，即插点法，枚举所有的中间点，再枚举所有的点对，对点对进行松弛操作
     * 多源最短路径指的是可以同时求出多个源点到其他点的最短路径，相当于多次执行dijkstra算法的效果
     * floyd算法算法与bellman ford算法类似，本质上也是基于的动态规划，进行松弛操作更新dp数组
     *
     * @param times
     * @param n
     * @param k
     * @return
     */
    public static int networkDelayTime9(int[][] times, int n, int k) {
        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        for (int[] time : times) {
            int from = time[0];
            int to = time[1];
            int weight = time[2];
            dist[from][to] = weight;
        }
        // floyd算法
        floyed(n, dist);
        int ans = -1;
        for (int i = 1; i <= n; i++) {
            if (dist[k][i] == Integer.MAX_VALUE) {
                return -1;
            }
            ans = Math.max(ans, dist[k][i]);
        }
        return ans;
    }

    private static void floyed(int n, int[][] dist) {
        for (int mid = 1; mid <= n; mid++) {
            for (int from = 1; from <= n; from++) {
                for (int to = 1; to <= n; to++) {
                    // 如果插入的点到点对的距离为无穷大，则必然不可能更新点对间的最短距离，跳过
                    if (dist[from][mid] == Integer.MAX_VALUE || dist[mid][to] == Integer.MAX_VALUE) {
                        continue;
                    }
                    dist[from][to] = Math.min(dist[from][to], dist[from][mid] + dist[mid][to]);
                }
            }
        }
    }

    /**
     * dijkstra算法 求最大概率及路径
     *
     * @param n
     * @param edges
     * @param succProb
     * @param start
     * @param end
     * @return
     */
    public static double maxProbability(int n, int[][] edges, double[] succProb, int start, int end) {
        List<List<double[]>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        // 无向加权图
        for (int i = 0; i < edges.length; i++) {
            int from = edges[i][0];
            int to = edges[i][1];
            // 权重即为成功概率
            double w = succProb[i];
            // 无向图
            graph.get(from).add(new double[]{to, w});
            graph.get(to).add(new double[]{from, w});
        }

        double[] prob = new double[n];
        // 初始时源点到达其他点的成功概率都是0
        Arrays.fill(prob, 0);
        // 源点到达源点的成功概率为1
        prob[start] = 1;
        // 记录到达当前节点的上一个节点
        int[] lastPoint = new int[n];
        // 源点的上一个节点认为是自己，类似于并查集的写法
        lastPoint[start] = start;

        dijkstra(n, prob, graph, lastPoint);

        // 拼接路径
        StringBuilder path = new StringBuilder();
        int cur = end;
        path.append(cur);
        while (lastPoint[cur] != cur) {
            path.insert(0, lastPoint[cur] + " -> ");
            cur = lastPoint[cur];
        }
        // 本题无需输出所经过的路径
        System.out.println(path);

        // 返回源点到终点的最大成功概率
        return prob[end];
    }

    private static void dijkstra(int n, double[] prob, List<List<double[]>> graph, int[] lastPoint) {
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            int index = -1;
            for (int j = 0; j < n; j++) {
                if (visited[j]) {
                    continue;
                }
                if (index == -1) {
                    index = j;
                    continue;
                }
                if (prob[j] > prob[index]) {
                    index = j;
                }
            }
            double curProb = prob[index];
            visited[index] = true;
            List<double[]> edgeList = graph.get(index);
            for (double[] edge : edgeList) {
                int to = (int) edge[0];
                double weight = edge[1];
                if (prob[to] < curProb * weight) {
                    prob[to] = curProb * weight;
                    lastPoint[to] = index;
                }
            }
        }
    }

    public static void initDist(int n, int[][] dist) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }
    }

    public static void updateDist(int n, int[][] dist) {
        for (int mid = 0; mid < n; mid++) {
            for (int left = 0; left < n; left++) {
                for (int right = 0; right < n; right++) {
                    if (dist[left][mid] == Integer.MAX_VALUE || dist[mid][right] == Integer.MAX_VALUE) {
                        continue;
                    }
                    dist[left][right] = Math.min(dist[left][right], dist[left][mid] + dist[mid][right]);
                }
            }
        }
    }

    public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] dist = new int[n][n];
        initDist(n, dist);

        // 无向图
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            dist[from][to] = weight;
            dist[to][from] = weight;
        }

        // floyd算法
        updateDist(n, dist);

        int[] count = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][j] <= distanceThreshold) {
                    count[i]++;
                }
            }
        }

        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            if (o1[1] != o2[1]) {
                return o1[1] - o2[1];
            } else {
                return o2[0] - o1[0];
            }
        });
        for (int i = 0; i < n; i++) {
            queue.add(new int[]{i, count[i]});
        }

        return Objects.requireNonNull(queue.poll())[0];
    }

    /**
     * 广度优先搜索
     *
     * @param maze
     * @param start
     * @param dest
     * @return
     */
    public static int shortestDistance3(int[][] maze, int[] start, int[] dest) {
        int[][] distance = new int[maze.length][maze[0].length];
        for (int[] row : distance) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        distance[start[0]][start[1]] = 0;
        bfs(maze, start, distance);
        if (distance[dest[0]][dest[1]] == Integer.MAX_VALUE) {
            return -1;
        }
        return distance[dest[0]][dest[1]];
    }

    private static void bfs(int[][] maze, int[] start, int[][] distance) {
        int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int[] s = queue.remove();
            for (int[] dir : dirs) {
                int x = s[0] + dir[0];
                int y = s[1] + dir[1];
                int count = 0;
                while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
                    count++;
                }
                if (distance[s[0]][s[1]] + count < distance[x - dir[0]][y - dir[1]]) {
                    distance[x - dir[0]][y - dir[1]] = distance[s[0]][s[1]] + count;
                    queue.add(new int[]{x - dir[0], y - dir[1]});
                }
            }
        }
    }

    /**
     * 深度优先搜索
     *
     * @param maze
     * @param start
     * @param dest
     * @return
     */
    public static int shortestDistance2(int[][] maze, int[] start, int[] dest) {
        int[][] distance = new int[maze.length][maze[0].length];
        for (int[] row : distance)
            Arrays.fill(row, Integer.MAX_VALUE);
        distance[start[0]][start[1]] = 0;
        dfs(maze, start, distance);
        if (distance[dest[0]][dest[1]] == Integer.MAX_VALUE) {
            return -1;
        }
        return distance[dest[0]][dest[1]];
    }

    public static void dfs(int[][] maze, int[] start, int[][] distance) {
        int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        for (int[] dir : dirs) {
            int x = start[0] + dir[0];
            int y = start[1] + dir[1];
            int count = 0;
            while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
                x += dir[0];
                y += dir[1];
                count++;
            }
            if (distance[start[0]][start[1]] + count < distance[x - dir[0]][y - dir[1]]) {
                distance[x - dir[0]][y - dir[1]] = distance[start[0]][start[1]] + count;
                dfs(maze, new int[]{x - dir[0], y - dir[1]}, distance);
            }
        }
    }

    /**
     * 迪杰斯特拉算法
     *
     * @param maze
     * @param start
     * @param dest
     * @return
     */
    public static int shortestDistance(int[][] maze, int[] start, int[] dest) {
        int m = maze.length;
        int n = maze[0].length;

        int[][] distance = new int[m][n];
        boolean[][] visited = new boolean[m][n];

        for (int[] row : distance) {
            // 默认所有点均不可达
            Arrays.fill(row, Integer.MAX_VALUE);
        }

        // 源点的最短距离为0
        distance[start[0]][start[1]] = 0;

        // 求最短路径
        dijkstra(maze, distance, visited);

        // 判断终点是否可达，距离为无穷大即为不可达，返回-1
        if (distance[dest[0]][dest[1]] == Integer.MAX_VALUE) {
            return -1;
        }
        return distance[dest[0]][dest[1]];
    }

    public static void dijkstra(int[][] maze, int[][] distance, boolean[][] visited) {
        int[][] dirs = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
        while (true) {
            // 找到当前距离最短的点
            int[] from = {-1, -1};
            // 默认最小值为无穷大
            int min_val = Integer.MAX_VALUE;

            // 遍历整个地图寻找当前最短路径最小的节点
            for (int i = 0; i < distance.length; i++) {
                for (int j = 0; j < distance[0].length; j++) {
                    // 这里的判断会跳过墙
                    // 因为墙的位置默认是无穷大，并且在后续不会发生变更
                    if (!visited[i][j] && distance[i][j] < min_val) {
                        from = new int[]{i, j};
                        min_val = distance[i][j];
                    }
                }
            }

            // 找不到合法的点了，算法结束
            int fromX = from[0];
            int fromY = from[1];
            // 无法使用迭代，因为事先不知道图中有多少个节点，不过可以使用堆优化的dijkstra算法
            if (fromX < 0) {
                break;
            }

            // 标记当前节点为已访问
            visited[fromX][fromY] = true;
            // 遍历四个方向，即遍历与当前from节点相连的四个节点
            for (int[] dir : dirs) {
                int toX = fromX + dir[0];
                int toY = fromY + dir[1];
                int count = 0;
                // 统计空地数量，同一方向走到墙为止
                // 计算边的权重
                while (toX >= 0 && toY >= 0 && toX < maze.length && toY < maze[0].length && maze[toX][toY] == 0) {
                    // 退出循环时，这里多移动了一格，多加了一次，在后续需要减去一个单位格
                    toX += dir[0];
                    toY += dir[1];
                    count++;
                }
                // 更新最短距离
                // 上方循环多走了一格，需要减去一个单元格才是靠近墙的节点坐标
                if (distance[fromX][fromY] + count < distance[toX - dir[0]][toY - dir[1]]) {
                    // 到达墙壁的位置即为图的一个节点，使用当前节点加上权重更新靠近墙壁节点的最短距离
                    distance[toX - dir[0]][toY - dir[1]] = distance[fromX][fromY] + count;
                }
            }
        }
    }

    public static int minimumCost(int n, int[][] connections) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        queue.addAll(Arrays.asList(connections));
        // 城市编号是 1 到 n
        UnionFind unionFind = new UnionFind(n + 1);

        int ans = 0;
        int count = 0;
        while (queue.size() > 0) {
            if (count == n - 1) {
                break;
            }
            int[] edge = queue.poll();
            int point1 = edge[0];
            int point2 = edge[1];
            int weight = edge[2];
            if (!unionFind.isConnected(point1, point2)) {
                unionFind.union(point1, point2);
                count++;
                ans += weight;
            }
        }

        if (count != n - 1) {
            return -1;
        }
        return ans;
    }

    /**
     * Kruskal Algorithm
     *
     * @param points
     * @return
     */
    public static int minCostConnectPoints(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }

        int n = points.length;
        // 按照权值升序排序
        PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x.weight));

        // 并查集数组大小即为节点个数，n个节点
        UnionFind uf = new UnionFind(n);

        // 计算任意两点之间的权重，加入队列
        for (int from = 0; from < n; from++) {
            for (int to = from + 1; to < n; to++) {
                int[] coordinate1 = points[from];
                int[] coordinate2 = points[to];
                // Calculate the distance between two coordinates.
                int cost = Math.abs(coordinate1[0] - coordinate2[0]) + Math.abs(coordinate1[1] - coordinate2[1]);
                // 无向边
                Edge edge = new Edge(from, to, cost, false);
                // 加入优先队列
                queue.add(edge);
            }
        }

        // 最小生成树中边的权重之和
        int result = 0;
        // 最小生成树中的边数
        int count = 0;
        while (true) {
            // 如果队列为空，表示所有的边都已经用完，结束算法
            if (queue.size() == 0) {
                break;
            }
            // 弹出权值最小的边
            Edge e = queue.poll();
            // 判断边的两个端点是否已经连通，如果已经连通，说明不能加入当前边，否则会形成环
            if (!uf.isConnected(e.point1, e.point2)) {
                // 如果当前边还不在最小生成树中，加入当前边
                uf.union(e.point1, e.point2);
                // 叠加边的权重
                result += e.weight;
                // 最小生成树找到了一条边，边数加一
                count++;
                // 如果已经找到了n-1条边，则结束算法
                if (count == n - 1) {
                    break;
                }
            }
        }

        // 如果边数达不到n-1，表示不能形成最小生成树
        if (count < n - 1) {
            return -1;
        }
        return result;
    }


    /**
     * tarjan算法
     *
     * @param n
     * @param connections
     * @return
     */
    @Deprecated
    public static List<List<Integer>> criticalConnections1(int n, List<List<Integer>> connections) {
        // 常规生成邻接表
        List<List<Integer>> graph = new ArrayList<>();
        buildGraph(n, connections, graph);

        List<List<Integer>> result = new ArrayList<>();
        int[] firstVisitedTimeStamp = new int[n]; // dfs过程中，初次访问某个节点时的时间戳
        int[] minTimeStamp = new int[n]; // 每个节点能访问到的节点的最小时间戳
        int[] autoIncNum = {0}; // 自增数字，用来赋值给节点的时间戳
        int startPoint = 0;
        int beforePoint = 0;
        dfs(startPoint, beforePoint, graph, firstVisitedTimeStamp, minTimeStamp, result, autoIncNum); // 从顶点 0 开始dfs，并认为其 前驱节点为 0
        return result;
    }

    @Deprecated
    private static void dfs(int curPoint, int beforePoint, List<List<Integer>> graph, int[] firstVisitedTimeStamp, int[] minTimeStamp, List<List<Integer>> result, int[] autoIncNum) {
        // 更新时间戳
        autoIncNum[0]++;
        int curNum = autoIncNum[0];
        // 记录初次被访问时的时间戳
        firstVisitedTimeStamp[curPoint] = curNum;
        // 默认当前节点的最小时间戳为自身的时间戳
        minTimeStamp[curPoint] = curNum;

        // 遍历相邻的所有节点
        List<Integer> connectedNodes = graph.get(curPoint);
        for (int connectedNode : connectedNodes) {
            // 没有记录过首次访问的时间戳，意味着之前没有被访问过
            if (firstVisitedTimeStamp[connectedNode] == 0) {
                // 代表dfs发现新节点
                // 进入这个新节点
                dfs(connectedNode, curPoint, graph, firstVisitedTimeStamp, minTimeStamp, result, autoIncNum);

                // 更新当前节点的最小时间戳
                minTimeStamp[curPoint] = Math.min(minTimeStamp[curPoint], minTimeStamp[connectedNode]);

                // 如果相邻节点的最小时间戳大于当前节点的首次访问时间戳
                if (minTimeStamp[connectedNode] > firstVisitedTimeStamp[curPoint]) {
                    // 说明当前节点curPoint到达该相邻节点connectedNode的时间相较于connectedNode连接的其他节点而言更早
                    // 发现桥边，添加到结果集
                    result.add(Arrays.asList(curPoint, connectedNode));
                }
            } else if (firstVisitedTimeStamp[connectedNode] < firstVisitedTimeStamp[curPoint] && connectedNode != beforePoint) {
                // connectedNode 已经在 curPoint 之前被访问过了。因为是无向图，curPoint 可以反向访问到其 【dfs搜索树】上的父节点，此时需要跳过。
                minTimeStamp[curPoint] = Math.min(minTimeStamp[curPoint], firstVisitedTimeStamp[connectedNode]);
                // 这里为什么用 firstVisitedTimeStamp[connectedNode] 而不用 minTimeStamp[connectedNode]，我一开始真的很困惑。
                // 在这道题的场景下，二者其实都可以。
//                minTimeStamp[curPoint] = Math.min(minTimeStamp[curPoint], minTimeStamp[connectedNode]);
            }
            //else if(firstVisitedTimeStamp[connectedNode] > firstVisitedTimeStamp[curPoint]){} // 无需被处理
        }
    }

    /**
     * targan算法
     *
     * @param n
     * @param connections
     * @return
     */
    public static List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
        // 构建一个map，存放每个节点的相邻节点有哪些
        Map<Integer, Set<Integer>> map = new HashMap<>();
        buildMap(connections, map);

        // 创建一个数组，存放每个节点的id是什么
        int[] id = new int[n];
        Arrays.fill(id, -1);

        // 选取一个点作为根节点，dfs向下递归，过程中识别出哪个边是critical connection
        List<List<Integer>> res = new ArrayList<>();
        dfs(0, 0, -1, id, map, res);    // 假设根节点有一个编号是-1父节点

        return res;
    }

    public static int dfs(int node, int nodeID, int parent, int[] id, Map<Integer, Set<Integer>> map, List<List<Integer>> res) {
        id[node] = nodeID;

        Set<Integer> set = map.get(node);
        for (Integer neighbor : set) {
            if (neighbor == parent) {
                continue;
            } else if (id[neighbor] == -1) {
                id[node] = Math.min(id[node], dfs(neighbor, nodeID + 1, node, id, map, res));
            } else {
                id[node] = Math.min(id[node], id[neighbor]);
            }
        }

        if (id[node] == nodeID && node != 0) {
            res.add(Arrays.asList(parent, node));
        }

        return id[node];
    }

    public static void buildMap(List<List<Integer>> con, Map<Integer, Set<Integer>> map) {
        for (List<Integer> edge : con) {
            int n1 = edge.get(0);
            int n2 = edge.get(1);

            Set<Integer> n1n = map.getOrDefault(n1, new HashSet<>());
            Set<Integer> n2n = map.getOrDefault(n2, new HashSet<>());

            n1n.add(n2);
            n2n.add(n1);

            map.put(n1, n1n);
            map.put(n2, n2n);
        }
    }

    public static List<List<Integer>> criticalConnections2(int n, List<List<Integer>> connections) {
        List<List<Integer>> graph = new ArrayList<>();
        buildGraph(n, connections, graph);

        List<List<Integer>> result = new ArrayList<>();
        int startPoint = 0;
        int initId = 0;
        int[] ids = new int[n];
        Arrays.fill(ids, -1);
        int parent = -1;
        dfs(graph, result, startPoint, parent, initId, ids);
        return result;
    }

    public static List<List<Integer>> criticalConnections3(int n, List<List<Integer>> connections) {
        List<List<Integer>> graph = new ArrayList<>();
        buildGraph(n, connections, graph);

        List<List<Integer>> result = new ArrayList<>();
        int startPoint = 0;
        int initId = 0;
        int[] ids = new int[n];
        Arrays.fill(ids, -1);
        int parent = -1;
        dfs1(graph, result, startPoint, parent, initId, ids);
        return result;
    }

    private static int dfs(List<List<Integer>> graph, List<List<Integer>> result, int curNode, int parent, int curId, int[] ids) {
        // 初始id，先给一个可能的id
        ids[curNode] = curId;

        List<Integer> connectedNodes = graph.get(curNode);

        for (int neighbor : connectedNodes) {
            // 父结点跳过
            if (neighbor == parent) {
                continue;
            }
            // 相邻节点没有被访问过
            if (ids[neighbor] == -1) {
                // 探索下一个节点的id，并与当前节点相比较，如果相邻节点id更小，说明存在通路到达之前被访问过的节点，说明形成了环，也说明存在别的通路绕过父结点
                ids[curNode] = Math.min(ids[curNode], dfs(graph, result, neighbor, curNode, curId + 1, ids));
            } else {
                // 相邻节点已经被计算过id，直接比较id更新
                ids[curNode] = Math.min(ids[curNode], ids[neighbor]);
            }
        }

        // 当前节点id已经确定后，判断id与初始指定的id是否一致，不一致说明有别的通路能够绕到父结点或者父结点前面，存在环
        // 如果保持一致说明不存在别的通路绕过父结点，则当前节点与父结点之间的边即为关键连接
        // 如果当前节点的id比初始值小，说明在往下dfs的时候，遇到了一个之前计算过id的节点【节点A】，说明存在其他通路能够到达当前节点，意味着存在至少两条通路到达当前节点，说明当前节点必然位于环中
        // 通路一：顶点0 -> 父节点 -> 当前节点
        // 通路二：顶点0 -> A节点 -> 当前节点
        // 意味着 顶点0 存在至少两条路径到达当前节点，意味着顶点0到达在某个位置进入了一个环，当前节点位于这个环中
        if (ids[curNode] == curId && curNode != 0) {
            result.add(Arrays.asList(parent, curNode));
        }

        return ids[curNode];
    }

    private static void buildGraph(int n, List<List<Integer>> connections, List<List<Integer>> graph) {
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        // 构建无向图
        for (List<Integer> connection : connections) {
            int from = connection.get(0);
            int to = connection.get(1);
            graph.get(from).add(to);
            graph.get(to).add(from);
        }
    }

    /**
     * 发现dfs方法可以简化，本质上就是要求得所有相邻节点的id，再更新当前节点的id
     * 最后判断当前节点id有没有被更新，如果没有被更新，说明当前节点的与父结点之间的边为关键路径
     *
     * @param graph
     * @param result
     * @param curNode
     * @param parent
     * @param curId
     * @param ids
     */
    private static void dfs1(List<List<Integer>> graph, List<List<Integer>> result, int curNode, int parent, int curId, int[] ids) {
        // 初始id，先给一个可能的id
        ids[curNode] = curId;

        List<Integer> connectedNodes = graph.get(curNode);

        for (int neighbor : connectedNodes) {
            // 父结点跳过
            if (neighbor == parent) {
                continue;
            }
            // 相邻节点id还没有计算过
            if (ids[neighbor] == -1) {
                // 计算节点id
                dfs1(graph, result, neighbor, curNode, curId + 1, ids);
            }
            // 比较当前节点与相邻节点的id，相邻节点id更小则更新当前节点的id，目的是为了使环上的所有节点都以环中节点最小的id为准，从而使得环的所有节点id保持一致，进而视作一个大节点
            ids[curNode] = Math.min(ids[curNode], ids[neighbor]);
        }

        // 当前节点id已经确定后，判断id与初始指定的id是否一致，不一致说明有别的通路能够绕到父结点前面，存在环
        // 如果保持一致说明不存在别的通路绕过父结点，则当前节点与父结点之间的边即为关键连接
        if (ids[curNode] == curId && curNode != 0) {
            result.add(Arrays.asList(parent, curNode));
        }
    }

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        List<List<Integer>> graph = new ArrayList<>();
        Map<String, Integer> wordIdMap = new HashMap<>();

        int[] id = {0};
        // 构建无向图
        buildGraph(beginWord, wordList, graph, wordIdMap, id);

        // 判断单词集合是否包含结束单词
        if (!wordIdMap.containsKey(endWord)) {
            return 0;
        }

        // 获取起点和终点顶点id
        int startNodeId = wordIdMap.get(beginWord);
        int endNodeId = wordIdMap.get(endWord);

        // 获取终点所在层高，起点层高为0
        return bfs(graph, id, startNodeId, endNodeId);
    }

    private static int bfs(List<List<Integer>> graph, int[] id, int startNodeId, int endNodeId) {
        // BFS获取最短路径长度
        Queue<Integer> queue = new LinkedList<>();
        // 起点加入队列
        queue.add(startNodeId);
        // 判断节点是否已经被访问
        boolean[] visited = new boolean[id[0]];
        visited[startNodeId] = true;
        // 节点层高
        int level = -1;
        while (queue.size() > 0) {
            int size = queue.size();
            level++;
            for (int i = 0; i < size; i++) {
                Integer curNode = queue.poll();
                if (curNode == null) {
                    throw new RuntimeException("队列中节点为空");
                }
                // 能够到达终点，返回答案
                if (curNode == endNodeId) {
                    return level / 2 + 1;
                }
                List<Integer> nodes = graph.get(curNode);
                // 相邻节点入队
                for (Integer node : nodes) {
                    if (visited[node]) {
                        continue;
                    }
                    queue.add(node);
                    visited[node] = true;
                }
            }
        }
        // 无法到达终点
        return 0;
    }


    private static void buildGraph(String beginWord, List<String> wordList, List<List<Integer>> graph, Map<String, Integer> wordIdMap, int[] id) {
        addWord(beginWord, graph, id, wordIdMap);
        for (String s : wordList) {
            addWord(s, graph, id, wordIdMap);
        }
    }

    private static void addWord(String word, List<List<Integer>> graph, int[] id, Map<String, Integer> wordIdMap) {
        addNode(graph, id, wordIdMap, word);
        // 端点1
        int from = wordIdMap.get(word);
        // 生成当前节点的虚拟节点，并加入图
        for (int i = 0; i < word.length(); i++) {
            String str = word.substring(0, i) + "*" + word.substring(i + 1);
            // 节点不存在，添加节点
            if (wordIdMap.get(str) == null) {
                addNode(graph, id, wordIdMap, str);
            }
            // 将新形成的边加入图
            addEdge(graph, wordIdMap, from, str);
        }
    }

    private static void addEdge(List<List<Integer>> graph, Map<String, Integer> wordIdMap, int from, String str) {
        // 端点2
        int to = wordIdMap.get(str);
        // 构建无向图
        graph.get(from).add(to);
        graph.get(to).add(from);
    }

    private static void addNode(List<List<Integer>> graph, int[] id, Map<String, Integer> wordIdMap, String str) {
        // 新建节点
        graph.add(new ArrayList<>());
        wordIdMap.put(str, id[0]++);
    }

    /**
     * 解答错误
     *
     * @param grid
     * @return
     */
    public static int shortestPathAllKeys(String[] grid) {
        int m = grid.length;
        int n = grid[0].length();
        char[][] matrix = new char[m][n];
        for (int i = 0; i < grid.length; i++) {
            matrix[i] = grid[i].toCharArray();
        }
        int keyMask = 0;
        int[] start = new int[]{-1, -1, keyMask};
        Set<Character> locks = new HashSet<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '@') {
                    start = new int[]{i, j, keyMask};
                    continue;
                }
                if (Character.isUpperCase(matrix[i][j])) {
                    locks.add(matrix[i][j]);
                }
            }
        }
        int lockMask = 0;
        for (Character c : locks) {
            lockMask |= 1 << ((int) c - 65);
        }
        if (start[0] == -1) {
            return -1;
        }
        Queue<int[]> queue = new LinkedList<>();
        queue.add(start);
        int[][] dist = new int[m][n];
        for (int[] ints : dist) {
            Arrays.fill(ints, Integer.MAX_VALUE);
        }
        dist[start[0]][start[1]] = 0;
        int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int step = -1;
        while (queue.size() > 0) {
            int size = queue.size();
            step++;
            for (int i = 0; i < size; i++) {
                int[] curNode = queue.poll();
                int key = Objects.requireNonNull(curNode)[2];
                if (key == lockMask) {
                    return step;
                }
                for (int[] dir : dirs) {
                    int newX = curNode[0] + dir[0];
                    int newY = curNode[1] + dir[1];
                    // 越界
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n) {
                        continue;
                    }
                    // 节点已有路径小于当前路径长度
                    if (dist[newX][newY] < step + 1) {
                        continue;
                    }
                    char c = matrix[newX][newY];
                    // 墙
                    if (c == '#') {
                        // 不能进
                        continue;
                    }
                    if (Character.isLowerCase(c)) {
                        // 钥匙
                        // 更新钥匙
                        int newKey = key | 1 << ((int) c - 97);
                        // 进入
                        queue.add(new int[]{newX, newY, newKey});
                        dist[newX][newY] = step + 1;
                    } else if (Character.isUpperCase(c)) {
                        // 锁
                        int lock = 1 << ((int) c - 65);
                        // 当前拿到的钥匙能够打开锁
                        if ((key & lock) != 0) {
                            // 进入
                            queue.add(new int[]{newX, newY, key});
                            dist[newX][newY] = step + 1;
                        }
                    } else {
                        // 空房间，直接进
                        queue.add(new int[]{newX, newY, key});
                        dist[newX][newY] = step + 1;
                    }
                }
            }
        }
        return -1;
    }

    public static int shortestPathAllKeys1(String[] grid) {

        int N = 35;
        int K = 10;
        int INF = 0x3f3f3f3f;
        int[][][] dist = new int[N][N][1 << K];
        int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int n = grid.length;
        int m = grid[0].length();
        int cnt = 0;

        Deque<int[]> d = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                Arrays.fill(dist[i][j], INF);
                char c = grid[i].charAt(j);
                if (c == '@') {
                    d.addLast(new int[]{i, j, 0});
                    dist[i][j][0] = 0;
                } else if (c >= 'a' && c <= 'z') {
                    cnt++;
                }
            }
        }
        while (!d.isEmpty()) {
            int[] info = d.pollFirst();
            int x = info[0];
            int y = info[1];
            int cur = info[2];
            int step = dist[x][y][cur];
            for (int[] di : dirs) {
                int nx = x + di[0];
                int ny = y + di[1];
                if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                    continue;
                }
                char c = grid[nx].charAt(ny);
                if (c == '#') {
                    continue;
                }
                if ((c >= 'A' && c <= 'Z') && (cur >> (c - 'A') & 1) == 0) {
                    continue;
                }
                int ncur = cur;
                if (c >= 'a' && c <= 'z') {
                    ncur |= 1 << (c - 'a');
                }
                if (ncur == (1 << cnt) - 1) {
                    return step + 1;
                }
                if (step + 1 >= dist[nx][ny][ncur]) {
                    continue;
                }
                dist[nx][ny][ncur] = step + 1;
                d.addLast(new int[]{nx, ny, ncur});
            }
        }
        return -1;

    }

    public static int numSimilarGroups(String[] strs) {
        int n = strs.length;
        UnionFind unionFind = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                if (unionFind.isConnected(i, j)) {
                    continue;
                }
                if (isSimilar(strs[i], strs[j])) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.getCount();
    }

    private static boolean isSimilar(String str1, String str2) {
        if (str1.equals(str2)) {
            return true;
        }
        char[] cs1 = new char[2];
        char[] cs2 = new char[2];
        int diff = 0;
        for (int i = 0; i < str1.length(); i++) {
            if (str1.charAt(i) == str2.charAt(i)) {
                continue;
            }
            if (diff == 2) {
                return false;
            }
            cs1[diff] = str1.charAt(i);
            cs2[diff] = str2.charAt(i);
            diff++;
        }
        return cs1[0] == cs2[1] && cs1[1] == cs2[0];
    }

    /**
     * 拓扑排序
     *
     * @param words
     * @return
     */
    public static String alienOrder(String[] words) {
        int n = words.length;

        // 获取所有的顶点
        Set<Character> nodes = getNodes(words);

        // 给顶点编号
        Map<Character, Integer> charToIdMap = new HashMap<>();
        Map<Integer, Character> idToCharMap = new HashMap<>();
        int id = 0;
        for (Character c : nodes) {
            charToIdMap.put(c, id);
            idToCharMap.put(id, c);
            id++;
        }

        // 构建有向图
        int[] inDegree = new int[nodes.size()];
        List<List<Integer>> graph = new ArrayList<>();
        String res = buildGraph(words, n, nodes, charToIdMap, inDegree, graph);
        if (Objects.equals(res, "")) {
            return res;
        }

        StringBuilder ans = new StringBuilder();

        // 初始将所有入度为0的点入队
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < inDegree.length; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }

        // BFS查找拓扑序列
        bfs(idToCharMap, inDegree, graph, ans, queue);

        // 如果拓扑序列长度小于顶点数量，说明不存在完整的拓扑序列
        if (ans.length() != nodes.size()) {
            return "";
        }

        return ans.toString();
    }

    private static String buildGraph(String[] words, int n, Set<Character> nodes, Map<Character, Integer> charToIdMap, int[] inDegree, List<List<Integer>> graph) {
        for (int i = 0; i < nodes.size(); i++) {
            graph.add(new ArrayList<>());
        }
        // 遍历所有的字符串大小关系
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = compareString(words, i, j);
                // 如果两个字符串没有字符不一致
                if (diff == -1) {
                    // 如果前者长度更长，违背排序规则
                    if (words[j].length() < words[i].length()) {
                        return "";
                    }
                    // 没有得到新的字符关系，不建立新的边
                    continue;
                }
                // 找到新的字符大小关系
                // 加入新的有向边
                addEdge(words, charToIdMap, inDegree, graph, i, j, diff);
            }
        }
        return null;
    }

    private static int compareString(String[] words, int i, int j) {
        int diff = -1;
        int len = Math.min(words[i].length(), words[j].length());
        for (int k = 0; k < len; k++) {
            if (words[i].charAt(k) == words[j].charAt(k)) {
                continue;
            }
            diff = k;
            break;
        }
        return diff;
    }

    private static void addEdge(String[] words, Map<Character, Integer> charToIdMap, int[] inDegree, List<List<Integer>> graph, int i, int j, int diff) {
        char ci = words[i].charAt(diff);
        char cj = words[j].charAt(diff);
        Integer from = charToIdMap.get(ci);
        Integer to = charToIdMap.get(cj);
        graph.get(from).add(to);
        // 入度更新
        inDegree[to]++;
    }

    private static void bfs(Map<Integer, Character> idToCharMap, int[] inDegree, List<List<Integer>> graph, StringBuilder ans, Queue<Integer> queue) {
        while (queue.size() > 0) {
            Integer curNode = queue.poll();
            ans.append(idToCharMap.get(curNode));
            List<Integer> neighbors = graph.get(curNode);
            for (Integer neighbor : neighbors) {
                // 入度更新
                inDegree[neighbor]--;
                // 入度为0则入队
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
    }

    private static Set<Character> getNodes(String[] words) {
        Set<Character> nodes = new HashSet<>();
        for (String word : words) {
            for (int j = 0; j < word.length(); j++) {
                nodes.add(word.charAt(j));
            }
        }
        return nodes;
    }

    public static int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        List<List<Integer>> groupItem = new ArrayList<>();
        for (int i = 0; i < n + m; ++i) {
            groupItem.add(new ArrayList<>());
        }

        // 组间和组内依赖图
        List<List<Integer>> groupGraph = new ArrayList<>();
        for (int i = 0; i < n + m; ++i) {
            groupGraph.add(new ArrayList<>());
        }
        List<List<Integer>> itemGraph = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            itemGraph.add(new ArrayList<>());
        }

        // 组间和组内入度数组
        int[] groupDegree = new int[n + m];
        int[] itemDegree = new int[n];

        List<Integer> id = new ArrayList<>();
        for (int i = 0; i < n + m; ++i) {
            id.add(i);
        }

        int leftId = m;
        // 给未分配的 item 分配一个 groupId
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId;
                leftId += 1;
            }
            groupItem.get(group[i]).add(i);
        }
        // 依赖关系建图
        for (int i = 0; i < n; ++i) {
            int curGroupId = group[i];
            for (int item : beforeItems.get(i)) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) {
                    itemDegree[i] += 1;
                    itemGraph.get(item).add(i);
                } else {
                    groupDegree[curGroupId] += 1;
                    groupGraph.get(beforeGroupId).add(curGroupId);
                }
            }
        }

        // 组间拓扑关系排序
        List<Integer> groupTopSort = topSort(groupDegree, groupGraph, id);
        if (groupTopSort.size() == 0) {
            return new int[0];
        }
        int[] ans = new int[n];
        int index = 0;
        // 组内拓扑关系排序
        for (int curGroupId : groupTopSort) {
            int size = groupItem.get(curGroupId).size();
            if (size == 0) {
                continue;
            }
            List<Integer> res = topSort(itemDegree, itemGraph, groupItem.get(curGroupId));
            if (res.size() == 0) {
                return new int[0];
            }
            for (int item : res) {
                ans[index++] = item;
            }
        }
        return ans;
    }

    public static List<Integer> topSort(int[] deg, List<List<Integer>> graph, List<Integer> items) {
        Queue<Integer> queue = new LinkedList<>();
        for (int item : items) {
            if (deg[item] == 0) {
                queue.offer(item);
            }
        }
        List<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()) {
            int u = queue.poll();
            res.add(u);
            for (int v : graph.get(u)) {
                if (--deg[v] == 0) {
                    queue.offer(v);
                }
            }
        }
        return res.size() == items.size() ? res : new ArrayList<>();
    }

    /**
     * 拓扑排序 + 动态规划
     *
     * @param colors
     * @param edges
     * @return
     */
    public static int largestPathValue(String colors, int[][] edges) {

        // 存储颜色id
        Map<Character, Integer> colorId = new HashMap<>();
        // 统计颜色数量同时给颜色编号
        int colorCount = getColorCount(colors, colorId);

        // 节点数量
        int n = colors.length();

        List<List<Integer>> graph = new ArrayList<>();
        // 构建有向图
        int[] inDegree = buildGraph(edges, n, graph);

        Queue<Integer> queue = new LinkedList<>();
        // 初始化队列，入度为0的节点入队
        int[][] dp = initQueue(colorCount, n, inDegree, queue);

        // bfs获取拓扑序列，同时计算dp数组
        List<Integer> list = bfs(colors, colorCount, colorId, graph, inDegree, queue, dp);

        // 没有完整的dp序列，说明图中有环
        if (list.size() != n) {
            return -1;
        }

        int max = 0;
        // 遍历dp数组获取答案
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < colorCount; j++) {
                max = Math.max(max, dp[i][j]);
            }
        }

        return max;
    }

    private static int getColorCount(String colors, Map<Character, Integer> colorId) {
        int id = 0;
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < colors.length(); i++) {
            if (!set.contains(colors.charAt(i))) {
                colorId.put(colors.charAt(i), id);
                id++;
                set.add(colors.charAt(i));
            }
        }
        return set.size();
    }

    private static List<Integer> bfs(String colors, int colorCount, Map<Character, Integer> colorId, List<List<Integer>> graph, int[] inDegree, Queue<Integer> queue, int[][] dp) {
        List<Integer> list = new ArrayList<>();
        while (queue.size() > 0) {
            Integer curNode = queue.poll();
            Integer curColorId = colorId.get(colors.charAt(curNode));
            dp[curNode][curColorId]++;
            list.add(curNode);
            List<Integer> neighbors = graph.get(curNode);
            for (Integer neighbor : neighbors) {
                // 所有的颜色都要尝试更新
                for (int i = 0; i < colorCount; i++) {
                    dp[neighbor][i] = Math.max(dp[curNode][i], dp[neighbor][i]);
                }
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }
        return list;
    }

    private static int[][] initQueue(int colorCount, int n, int[] inDegree, Queue<Integer> queue) {
        int[][] dp = new int[n][colorCount];
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.add(i);
            }
        }
        return dp;
    }

    private static int[] buildGraph(int[][] edges, int n, List<List<Integer>> graph) {
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] inDegree = new int[n];
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            graph.get(from).add(to);
            inDegree[to]++;
        }
        return inDegree;
    }

    /**
     * 超级水源 + kruskal算法
     *
     * @param n
     * @param wells
     * @param pipes
     * @return
     */
    public static int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        return kruskal(n, getPriorityQueue(wells, pipes));
    }

    /**
     * kruskal算法生成最小生成树，返回生成树的权值
     *
     * @param n
     * @param queue
     * @return
     */
    private static int kruskal(int n, PriorityQueue<int[]> queue) {
        int result = 0;
        int count = 0;
        // n + 1 个顶点
        UnionFind unionFind = new UnionFind(n + 1);
        while (queue.size() > 0) {
            int[] edge = queue.poll();
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            if (unionFind.isConnected(from, to)) {
                continue;
            }
            unionFind.union(from, to);
            count++;
            result += weight;
            // 已经选取了n条边，生成最小生成树结束
            if (count == n) {
                break;
            }
        }
        // 无法生成最小生成树
        if (count != n) {
            result = -1;
        }
        return result;
    }

    private static PriorityQueue<int[]> getPriorityQueue(int[] wells, int[][] pipes) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        // 添加超级水源到水井的边
        for (int i = 0; i < wells.length; i++) {
            int from = 0;
            int to = i + 1;
            int weight = wells[i];
            // 将带权边入队
            queue.add(new int[]{from, to, weight});
        }
        // 添加房子间的相连边
        for (int[] pipe : pipes) {
            int from = pipe[0];
            int to = pipe[1];
            int weight = pipe[2];
            // 将带权边入队
            queue.add(new int[]{from, to, weight});
        }
        return queue;
    }

    public static List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {

        List<List<Integer>> result = new ArrayList<>();
        // 关键边
        result.add(new ArrayList<>());
        // 伪关键边
        result.add(new ArrayList<>());
        PriorityQueue<int[]> queue = getPriorityQueue(edges, -1);
        int value = kruskal(n, queue, null);

        // 枚举所有的边
        for (int i = 0; i < edges.length; i++) {
            // 判断是否是关键边
            boolean isCritical = isCriticalEdge(n, edges, value, i);
            if (isCritical) {
                result.get(0).add(i);
                continue;
            }

            // 判断边是不是伪关键边
            boolean isPseudo = isPseudoCriticalEdge(n, edges, value, i);
            if (isPseudo) {
                result.get(1).add(i);
            }
        }

        return result;

    }

    private static boolean isPseudoCriticalEdge(int n, int[][] edges, int value, int i) {
        PriorityQueue<int[]> queue = getPriorityQueue(edges, -1);
        // 并查集优先连接当前边
        int v = kruskal(n, queue, edges[i]);
        return value == v;
    }

    private static boolean isCriticalEdge(int n, int[][] edges, int value, int i) {
        // 跳过当前边不加入队列
        PriorityQueue<int[]> queue = getPriorityQueue(edges, i);
        int v = kruskal(n, queue, null);
        return value != v;
    }

    private static int kruskal(int n, PriorityQueue<int[]> queue, int[] priorityEdge) {
        int count = 0;
        int value = 0;
        UnionFind unionFind = new UnionFind(n);
        // 优先连接的边
        if (priorityEdge != null) {
            unionFind.union(priorityEdge[0], priorityEdge[1]);
            count++;
            value += priorityEdge[2];
        }
        while (queue.size() > 0) {
            int[] edge = queue.poll();
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            if (unionFind.isConnected(from, to)) {
                continue;
            }
            unionFind.union(from, to);
            count++;
            value += weight;
            if (count == n - 1) {
                break;
            }
        }
        // 无法生成拓扑排序
        if (count != n - 1) {
            value = -1;
        }
        return value;
    }


    private static PriorityQueue<int[]> getPriorityQueue(int[][] edges, int skip) {
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[2]));
        for (int i = 0; i < edges.length; i++) {
            if (i == skip) {
                continue;
            }
            int from = edges[i][0];
            int to = edges[i][1];
            int weight = edges[i][2];
            // 构建无向图
            queue.add(new int[]{from, to, weight});
        }
        return queue;
    }

    /**
     * 超时
     *
     * @param nums
     * @return
     */
    public static boolean canTraverseAllPairs(int[] nums) {

        UnionFind unionFind = new UnionFind(nums.length);

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (!unionFind.isConnected(i, j) && gcd(nums[i], nums[j]) > 1) {
                    unionFind.union(i, j);
                }
            }
        }

        return unionFind.getCount() == 1;
    }

    /**
     * 超时
     *
     * @param nums
     * @return
     */
    public static boolean canTraverseAllPairs1(int[] nums) {

        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (gcd(nums[i], nums[j]) > 1) {
                    graph.get(i).add(j);
                    graph.get(j).add(i);
                }
            }
        }

        Queue<Integer> queue = new LinkedList<>();
        queue.add(0);
        boolean[] visited = new boolean[nums.length];
        visited[0] = true;
        while (queue.size() > 0) {
            Integer curNode = queue.poll();
            List<Integer> nodes = graph.get(curNode);
            for (Integer node : nodes) {
                if (visited[node]) {
                    continue;
                }
                queue.add(node);
                visited[node] = true;
            }
        }

        for (boolean b : visited) {
            if (!b) {
                return false;
            }
        }

        return true;
    }

    private static int gcd(int m, int n) {
        if (m < n) {
            int temp = m;
            m = n;
            n = temp;
        } else if (m == n) {
            return m;
        }
        while (n != 0) {
            int r = m % n;
            m = n;
            n = r;
        }
        return m;
    }

    public static boolean canTraverseAllPairs2(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        HashMap<Integer, HashSet<Integer>> map = new HashMap<>(), visited = new HashMap<>();
        for (int num : nums) {
            if (num == 1) {
                return false;
            }
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    list.add(i);
                    while (num % i == 0) {
                        num /= i;
                    }
                }
            }
            if (num > 1) {
                list.add(num);
            }
            map.putIfAbsent(list.get(0), new HashSet<>());
            for (int i = 1; i < list.size(); i++) {
                map.computeIfAbsent(list.get(i - 1), t -> new HashSet<>()).add(list.get(i));
                map.computeIfAbsent(list.get(i), t -> new HashSet<>()).add(list.get(i - 1));
            }
        }
        canTraverseAllPairs(map.keySet().iterator().next(), map, visited);
        return map.size() == visited.size();
    }

    private static void canTraverseAllPairs(int i, HashMap<Integer, HashSet<Integer>> map, HashMap<Integer, HashSet<Integer>> visited) {
        if (visited.put(i, new HashSet<>()) == null) {
            for (int j : map.get(i)) {
                canTraverseAllPairs(j, map, visited);
            }
        }
    }

    public static int maxIncreasingCells(int[][] mat) {

        return 0;
    }

//    public static Node cloneGraph(Node node) {
//        if (node == null) {
//            return null;
//        }
//        if (node.neighbors.isEmpty()) {
//            return new Node(node.val);
//        }
//        Queue<Pair<Node, Node>> queue = new LinkedList<>();
//        Set<Integer> visited = new HashSet<>();
//
//        Node result = new Node(node.val);
//        queue.add(new Pair<>(node, result));
//        visited.add(node.val);
//        Map<Integer, Node> nodeMap = new HashMap<>();
//        nodeMap.put(result.val, result);
//
//        while (!queue.isEmpty()) {
//            Pair<Node, Node> poll = queue.poll();
//            Node original = poll.getKey();
//            Node copied = poll.getValue();
//
//            for (int i = 0; i < original.neighbors.size(); i++) {
//                Node neighbor = original.neighbors.get(i);
//                Node newNode;
//                if (nodeMap.get(neighbor.val) == null) {
//                    // 节点不存在时需要新建节点
//                    newNode = new Node(neighbor.val);
//                    nodeMap.put(neighbor.val, newNode);
//                } else {
//                    // 节点已经存在，直接加入到邻接列表
//                    newNode = nodeMap.get(neighbor.val);
//                }
//                copied.neighbors.add(newNode);
//                if (visited.contains(neighbor.val)) {
//                    continue;
//                }
//                queue.add(new Pair<>(neighbor, newNode));
//                visited.add(neighbor.val);
//            }
//        }
//
//        return result;
//    }

//    private static final Map<Node, Node> visited = new HashMap<>();
//
//    public static Node cloneGraph(Node node) {
//        if (node == null) {
//            return null;
//        }
//
//        if (visited.containsKey(node)) {
//            return visited.get(node);
//        }
//
//        // 克隆当前节点（不包含邻居）
//        Node cloneNode = new Node(node.val, new ArrayList<>());
//        visited.put(node, cloneNode);
//
//        // 递归克隆邻居
//        for (Node neighbor : node.neighbors) {
//            cloneNode.neighbors.add(cloneGraph(neighbor));
//        }
//
//        return cloneNode;
//    }

    public static Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        Map<Node, Node> visited = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();

        queue.add(node);
        Node cloneNode = new Node(node.val);
        visited.put(node, cloneNode);

        while (!queue.isEmpty()) {
            Node curr = queue.poll();

            for (Node neighbor : curr.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    // 克隆邻居节点
                    visited.put(neighbor, new Node(neighbor.val));
                    queue.add(neighbor);
                }
                visited.get(curr).neighbors.add(visited.get(neighbor));
            }
        }

        return cloneNode;
    }

}
